Skip to content

2454. Next Greater Element IV 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  vector<int> secondGreaterElement(vector<int>& nums) {
    vector<int> ans(nums.size(), -1);
    // a decreasing stack that stores indices that met the first greater number
    stack<int> prevStack;
    // a decreasing stack that stores indices
    stack<int> currStack;

    for (int i = 0; i < nums.size(); ++i) {
      // Indices in `prevStack` meet the second greater number.
      while (!prevStack.empty() && nums[prevStack.top()] < nums[i])
        ans[prevStack.top()] = nums[i], prevStack.pop();
      // Push indices that meet the first greater number from `currStack` to
      // `prevStack`. We need a temporary array to make the indices in the
      // `prevStack` increasing.
      stack<int> decreasingIndices;
      while (!currStack.empty() && nums[currStack.top()] < nums[i])
        decreasingIndices.push(currStack.top()), currStack.pop();
      while (!decreasingIndices.empty())
        prevStack.push(decreasingIndices.top()), decreasingIndices.pop();
      currStack.push(i);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public int[] secondGreaterElement(int[] nums) {
    int[] ans = new int[nums.length];
    Arrays.fill(ans, -1);
    // a decreasing stack that stores indices that met the first greater number
    Deque<Integer> prevStack = new ArrayDeque<>();
    // a decreasing stack that stores indices
    Deque<Integer> currStack = new ArrayDeque<>();

    for (int i = 0; i < nums.length; ++i) {
      // Indices in prevStack meet the second greater num.
      while (!prevStack.isEmpty() && nums[prevStack.peek()] < nums[i])
        ans[prevStack.poll()] = nums[i];
      // Push indices that meet the first greater number from `currStack` to
      // `prevStack`. We need a temporary array to make the indices in the
      // `prevStack` increasing.
      Deque<Integer> decreasingIndices = new ArrayDeque<>();
      while (!currStack.isEmpty() && nums[currStack.peek()] < nums[i])
        decreasingIndices.push(currStack.poll());
      while (!decreasingIndices.isEmpty())
        prevStack.push(decreasingIndices.poll());
      currStack.push(i);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def secondGreaterElement(self, nums: List[int]) -> List[int]:
    ans = [-1] * len(nums)
    # a decreasing stack that stores indices that met the first greater number.
    prevStack = []
    # a decreasing stack that stores indices.
    currStack = []

    for i, num in enumerate(nums):
      # Indices in prevStack meet the second greater num.
      while prevStack and nums[prevStack[-1]] < num:
        ans[prevStack.pop()] = num
      # Push indices that meet the first greater number from `currStack` to
      # `prevStack`. We need a temporary array to make the indices in the
      # `prevStack` increasing.
      decreasingIndices = []
      while currStack and nums[currStack[-1]] < num:
        decreasingIndices.append(currStack.pop())
      while decreasingIndices:
        prevStack.append(decreasingIndices.pop())
      currStack.append(i)

    return ans