Stack - Question 1

Questions: We have an integer array with size n. The index of the first number is 0, and the last one is n-1. For each number, please find the index of the first number higher than it on the right side. If there is no such number, return -1.

Constains:

1 <= n <= 10^5

Analysis:

If we fix each number, then run a for loop for all the numbers on its right side in the array, we can find the first number that is larger. But the time complexity would be O(N^2) overall.

We need to find a solution that runs faster.

A stack can be used for this: since we are looking for the first element higher on the right side, we can maintain a monotonically decreasing order inside the stack. When scanning to a new number, 

1. if the stack is empty or the top element (the end of the numbers in the stack) is larger, just put the new number in the stack. Since the new number is smaller, the numbers in the stack still decreases;

2. if the stack is not empty and the top element is smaller than the new number, we need to pop up the top number, the first first larger number than it is just the new number!

3. we need to keep to do step 2 if the condition is still valid after popping out the top element;

4. when the condition in step2 becomes invalid, it becomes step 1;

5. after reaching the the last element, all the elements still inside the stack have no number larger than them on the right side, so we should return -1 for all of them.

Since this question asks for the index, so we need to store the index of the numbers in the stack, rather than the numbers.

See the code below:

class Solution {
public:
    vector<int> firstLargerIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        stack<int> sk;
        for(int i=0; i<n; ++i) {
            while(sk.size() && nums[sk.top()] < nums[i]) {
                res[sk.top()] = i;
                sk.pop();
            }
            sk.push(i);
        }
        return res;
    }
};

 Upper Layer