On monotonous stack

What is monotone stack ？

• A monotonous stack is actually a stack , It's just that the restrictions are more stringent than the normal stack . The requirement is that the elements must be ordered every time they are put on the stack （ If the new element does not stack as required , Then the previous elements will be put out of the stack , Wait until it meets the requirements ）, Make it form Monotone increasing / Monotonous delivery Minus a stack .

For example, we have an array ：

• Monotonically increasing stacks ： Only the younger ones go straight to the stack , If it is greater than, it will be put out of the stack first and then put into the stack （ You can do some operation calculation when you are out of the stack , For example, the problem of temperature is to calculate the distance between the first one greater than the value when it is put out of the stack ）. It is suitable for solving the first number of elements greater than the position

• Monotonically decreasing stacks ： Only the older ones are on the stack , If it's less than , It's also out of the stack first and then in the stack . It is suitable for finding the number of the first element less than the position

• How to judge is monotonous Increasing / Decline Stack It is decided by the order of the stack , For example, the stack is {1, 2, 6}, After leaving the stack , by {6, 2, 1}, This is in descending order , So it's a monotone decrement stack

Monotone stack is suitable for the problem of solving The first one is greater than xxx perhaps The first one is less than xxx This topic . When similar problems appear, we should give priority to using monotone stack to solve problems .

---

Let's take an example of a monotonically decreasing stack ：

• For example, we're going to put arrays {1, 3, 4, 5, 2, 9, 6} Push to stack ：

1. First 1 Push , Now the stack is ：{1}
2. Next is 3, because 3 > 1 , Direct stack , Now the stack is ：{1, 3}
3. Next is 4, because 4 > 3 , Direct stack , Now the stack is ：{1, 3, 4}
4. Next is 5, because 4 > 3 , Direct stack , Now the stack is ：{1, 3, 4, 5}
5. Next yes 2, because 2 < 5, Not meeting the conditions , So we're going to 5 Out of the stack , Now the stack is ：{1, 3, 4}
6. And then 2 And 4 Compare , because 2 < 4 , Still not meeting the conditions , So we will 4 Out of the stack , Now the stack is ：{1, 3}
7. And then 2 And 3 Compare , because 2 < 3 , Still not meeting the conditions , So we will 3 Out of the stack , Now the stack is ：{1}
8. And then 2 And 1 Compare , because 2 > 1 , Meet the conditions , take 2 Push , Now the stack is ：{1, 2}
9. Next is 9, because 9 > 2 , Direct stack , Now the stack is ：{1, 2, 9}
10. Next yes 6, because 6 < 9 , Not meeting the conditions , take 9 Out of the stack , Now the stack is ：{1, 2}
11. then 6 And 2 Compare ,6 > 2 , Meet the conditions ,6 Push , Now the stack is {1, 2, 6}
12. Last , The target array has been traversed , We get the result

---

Now there is such a topic ：

• Give you an array , Returns an array of equal length , The corresponding index stores the next larger element , If there's no bigger element , Save it -1. How to solve this ？
  • If the input is {2, 1, 2, 4, 3}, Then we'll get the results {4, 2, 4, -1, -1}
  • How did this result come from ？ Scan right , Than 2 The first big number is 4, Than 1 The first big number is 2, There's nothing like 4 Large number (4 > 3), There is no comparison. 3 Large number (3 == 3), So these two are -1

You can try to do this one ：739. Daily temperature

After many times to make a conclusion , It's not hard to find out , In fact, there is Pattern template Of , In the future, you just need to revise some ：

class Solution {
    public int[] monotonousStack(int[] T) {
        LinkedList<Integer> stack = new LinkedList<>();
        //  It is used to store the distance of the first element larger than the location 
        int[] res = new int[T.length];

        for (int i = 0; i < T.length; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int peek = stack.pop();
                // i - peek  It's the solution in peek On the right side of , The first one is greater than T[peek] The elements of 
                res[peek] = i - peek;
            }
            stack.push(i);
        }
        return res;
    }
}

「 Complexity analysis 」

• Time complexity ： Because the elements of an array can only be put on the stack at most , Once out of the stack , So the time complexity is still \(O(N)\) , among N Is array length
• Spatial complexity ： Because of the use of stacks , And the maximum stack length is the same as the array length , So the complexity of space is \(O(N)\), among N Is array length

For some time , If you're going to use arrays All elements , In other words, the elements in the stack will be put out of the stack finally , Well, it's very likely that we can't cross because we don't consider the boundary . So we can use it Sentinel law , stay {1, 3, 4, 5, 2, 9, 6} Add a... At the end -1 As sentinel , Turned into {1, 3, 4, 5, 2, 9, 6, -1} , This technique can simplify the code logic .