# Stack

#### [71. Simplify Path](https://leetcode.com/problems/simplify-path/)

Add Strings to stack, pop if meet `".."`.

```java
    public String simplifyPath(String path) {
        String[] strs = path.split("/");
        Stack<String> stack = new Stack<>();
        for (int i = 1; i < strs.length; i++) {
            if (strs[i].equals("..") && !stack.isEmpty()) {
                stack.pop();
            } else if (!strs[i].equals(".") 
                       && !strs[i].equals("..") 
                       && !strs[i].equals("")) {
                stack.add(strs[i]);
            }
        }
        StringBuilder sb = new StringBuilder("/");
        for (String s : stack) {
            sb.append(s).append("/");
        }
        return sb.length() != 1 
                ? sb.deleteCharAt(sb.length() - 1).toString() 
                : sb.toString();
    }
```

#### Next Greater Element

*Find the next greater element in array, if no such element, return -1.*

Pointer move from end to beginning, use a stack to store all element, but pop values which are smaller than the current value, this way we can keep a non-increasing sequence.

*T: O(n)  S: O(n)*

```java
public int[] nextGreaterElement(int[] nums) {
    Stack<Integer> stack = new Stack<>();
    int[] res = new int[nums.length];
    for (int i = nums.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
            stack.pop();
        }
        res[i] = stack.isEmpty() ? -1 : nums[stack.peek()];
        stack.add(i);
    }
    return res;
}
```

#### [155. Min Stack](https://leetcode.com/problems/min-stack/)

Before add new element. Add the previous `min` to the stack.&#x20;

{% tabs %}
{% tab title="Java" %}

```java
int min = Integer.MAX_VALUE;
Stack<Integer> stack;
/** initialize your data structure here. */
public MinStack() {
    stack = new Stack<>();
}

public void push(int x) {
    if (x <= min) {
        stack.add(min);
        min = x;
    }
    stack.add(x);
}

public void pop() {
    int pop = stack.pop();
    if (pop == min) {
        min = stack.pop();
    }
}

public int top() {
    return stack.peek();
}

public int getMin() {
    return min;
}
```

{% endtab %}

{% tab title="Python" %}

```python
def __init__(self):
    """
    initialize your data structure here.
    """
    self.stack = []
    self.minstack = []

def push(self, x: int) -> None:
    self.stack.append(x)
    if not self.minstack or x <= self.minstack[-1]:
        self.minstack.append(x)

def pop(self) -> None:
    pop = self.stack.pop()
    if self.minstack and self.minstack[-1] == pop:
        self.minstack.pop()

def top(self) -> int:
    return self.stack[-1]

def getMin(self) -> int:
    return self.minstack[-1]
```

{% endtab %}
{% endtabs %}

#### [Link](https://howardyangemail.gitbook.io/decode-leetcode/design#155-min-stack)

#### [232. Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/)

Use two stacks to flip to get queue.

```python
def __init__(self):
    self.s1 = []
    self.s2 = []

def push(self, x: int) -> None:
    self.s1.append(x)

def pop(self) -> int:
    if self.empty():
        return None
    if not self.s2:
        while self.s1:
            self.s2.append(self.s1.pop())
    return self.s2.pop()
    

def peek(self) -> int:
    if self.empty():
        return None
    if not self.s2:
        while self.s1:
            self.s2.append(self.s1.pop())
    return self.s2[-1]

def empty(self) -> bool:
    return not self.s1 and not self.s2
```

#### [150. Evaluate Reverse Polish Notation](https://leetcode.com/problems/evaluate-reverse-polish-notation/)

Loop over the token strings and add to a stack if it is a number. Alternatively run operation if it is an operator.

```java
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String t : tokens) {
            if ((t.equals("+") || t.equals("/") || t.equals("*") || t.equals("-"))  && !stack.isEmpty()) {
                int a = stack.pop();
                int b = stack.pop();
                if (t.equals("+")) {
                    stack.push(a + b);
                } else if (t.equals("-")) {
                    stack.push(b - a);
                } else if (t.equals("/")) {
                    stack.push(b / a);
                } else if (t.equals("*")) {
                    stack.push(a * b);
                }
            } else {
                stack.add(Integer.valueOf(t));
            }
        }
        return stack.pop();
    }
```

#### [394. Decode String](https://leetcode.com/problems/decode-string/)

Use two stacks, one to store result and the other one store numbers.&#x20;

* meet "\[", add to stack and reset current elements
* meet "]", pop from stack and aggregate results

```java
    public String decodeString(String s) {
        Stack<String> stack = new Stack<>();
        Stack<Integer> nstack = new Stack<>();
        String res = "";
        int num = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (Character.isLetter(c)) {
                res += c;
            } else if (c == '[') {
                stack.add(res);
                nstack.add(num);
                num = 0;
                res = "";
            } else if (c == ']' && !stack.isEmpty() && !nstack.isEmpty()) {
                StringBuilder sb = new StringBuilder(stack.pop());
                int n = nstack.pop();
                for (int k = 0; k < n; k++) {
                    sb.append(res);
                }
                res = sb.toString();
            }
        }
        return res;
    }
```

#### [739. Daily Temperatures](https://leetcode.com/problems/daily-temperatures/)

Same as the problem above. Answer is the distance between peek value and current index.

*T: O(n)  S: O(n)*

{% tabs %}
{% tab title="Java" %}

```java
    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[T.length];
        for (int i = T.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && T[stack.peek()] <= T[i]) {
                stack.pop();
            }
            res[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.add(i);
        }
        return res;
    }
```

{% endtab %}

{% tab title="Python" %}

```python
def dailyTemperatures(self, T: List[int]) -> List[int]:
    stack = []
    res = []
    for i in range(len(T) - 1, -1, -1):
        while stack and T[stack[-1]] <= T[i]:
            stack.pop()
        if stack:
            res.insert(0, stack[-1] - i)
        else:
            res.insert(0, 0)
        stack.append(i)
    return res
```

{% endtab %}
{% endtabs %}

#### [496. Next Greater Element I](https://leetcode.com/problems/next-greater-element-i/)

Refer to as Next Greater Element.&#x20;

*T: O(n)  S: O(n)*

{% tabs %}
{% tab title="Java" %}

```java
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<>();
    Stack<Integer> stack = new Stack<>();
    for (int i = nums2.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && nums2[stack.peek()] <= nums2[i]) {
            stack.pop();
        }
        if (!stack.isEmpty()) {
            map.put(nums2[i], nums2[stack.peek()]);
        }
        stack.add(i);
    }
    int[] res = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        if (map.get(nums1[i]) != null) {
            res[i] = map.get(nums1[i]);
        } else {
            res[i] = -1;
        }
    }
    return res;
}
```

{% endtab %}

{% tab title="Python" %}

```python
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
    stack = []
    dic = {}
    for i in range(len(nums2) - 1, -1, -1):
        while stack and stack[-1] < nums2[i]:
            stack.pop()
        if stack:
            dic[nums2[i]] = stack[-1]
        stack.append(nums2[i])
    res = []
    for i in range(len(nums1)):
        if nums1[i] in dic:
            res.append(dic[nums1[i]])
        else:
            res.append(-1)
    return res
```

{% endtab %}
{% endtabs %}

#### [503. Next Greater Element II](https://leetcode.com/problems/next-greater-element-ii/)

Since it is a circular array, one way is looping over the array **twice**, and maintain the stack and result array. While looping, mod i by n (`i % n`) as it points to the position on the current array.&#x20;

```java
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[n];
        for (int i = n * 2 - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i % n]) {
                stack.pop();
            }
            res[i % n] = stack.isEmpty() ? -1 : nums[stack.peek() % n];
            stack.add(i % n);
        }
        return res;
    }
```

#### [556. Next Greater Element III](https://leetcode.com/problems/next-greater-element-iii/)

1. If all digits sorted in descending order, then output is always “Not Possible”. For example, 4321.
2. If all digits are sorted in ascending order, then we need to swap last two digits. For example, 1234.
3. For other cases, we need to process the number from rightmost side (why? because we need to find the smallest of all greater numbers)

Algorithm:

1. Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “`534976`”, we stop at `4` because `4` is smaller than next digit `9`. If we do not find such a digit, then output is “Not Possible”.
2. Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “`534976`″, the right side of `4` contains “`976`”. The smallest digit greater than `4` is `6`.
3. Swap the above found two digits, we get `536974` in above example.

```java
    public int nextGreaterElement(int n) {
        char[] nums = String.valueOf(n).toCharArray();
        
        // 1. 
        int i = nums.length - 1;
        for (; i > 0; i--) {
            if (nums[i - 1] < nums[i]) break;
        }
        if (i == 0) return -1;
        
        // 2
        int x = nums[i - 1], j = i + 1, smallest = i;
        while (j < nums.length) {
            if (nums[j] > x && nums[smallest] >= nums[j]) smallest = j;
            j++;
        }
        // 3 
        char temp = nums[smallest];
        nums[smallest] = nums[i - 1];
        nums[i - 1] = temp;
        Arrays.sort(nums, i , nums.length);
        long val = Long.parseLong(new String(nums));
        return (val <= Integer.MAX_VALUE) ? (int)val : -1;
    }
```

#### [735. Asteroid Collision](https://leetcode.com/problems/asteroid-collision/)

Use stack to add element when it is positive. Otherwise, keep popping the previous one when it is smaller than opposite of current, for eg. `[2, 3, -10]`.

When current and previous are exactly opposite, such as `[8, -8]`, only pop. When the previous is negative, continue push current, eg `[-2, -1]`

```java
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int a : asteroids) {
            if (a > 0) { // a > 0
                stack.push(a);
            } else { // a > 0
                while (!stack.isEmpty() && stack.peek() < -a && stack.peek() > 0) {
                    stack.pop();
                }
                if (!stack.isEmpty() && stack.peek() == -a) {
                    stack.pop();
                } else if (stack.isEmpty() || stack.peek() < 0) {
                    stack.push(a);
                } 
            }
        }
        int[] res = new int[stack.size()];
        int i = 0;
        for (int n : stack) {
            res[i++] = n;
        }
        return res;
    }
```

#### [31. Next Permutation](https://leetcode.com/problems/next-permutation/)

Same as **556** above:

1. find the first increase element i from the right
2. find the first element larger than `i` from the right
3. swap `i` and `j`, reverse from `i + 1` to end.

```java
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) j--;
            swap(nums, i, j);
        }
        reverse(nums, i + 1, nums.length - 1);
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i++, j--);
        }
    }
```

#### [581. Shortest Unsorted Continuous Subarray](https://leetcode.com/problems/shortest-unsorted-continuous-subarray/)

Solution1: Sort and find the start and end of the difference: *O(nlogn)*

```java
public int findUnsortedSubarray(int[] nums) {
    int[] snums = nums.clone();
    Arrays.sort(nums);
    int start = nums.length, end = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != snums[i]) {
            start = Math.min(start, i);
            end = Math.max(end, i);
        }
    }
    if (end - start >= 0) {
        return end - start + 1;
    }
    return 0;
}
```

Solution1: **Use Monotonic stack to find the smallest start index where it violates the increasing trend. Also find the largest end where it violates the decreasing trend from the back**. O(n)

```java
public int findUnsortedSubarray(int[] nums) {
    Stack<Integer> stack = new Stack<>();
    int start = nums.length, end = 0;
    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
            start = Math.min(start, stack.pop());
        }
        stack.add(i);
    }
    stack.clear();
    for (int i = nums.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            end = Math.max(end, stack.pop());
        }
        stack.add(i);
    }
    if (end - start <= 0) return 0;
    return end - start + 1;
}
```

#### [239. Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/)

Maintain a deque while going through Keep only the indexes of elements from the current sliding window. Remove indexes of all elements smaller than the current one, since they will not be the maximum ones.

```java
public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new LinkedList<>();
    // initiate a result array with size n - k + 1
    int[] res = new int[nums.length - k + 1]; 
    for (int i = 0; i < nums.length; i++) {
        // pop First when your first index element exceeds window
        while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
            deque.pollFirst();
        }    
        // keep popping from last when your last element is smaller or equals current num, 
        // which means all element in the deque is larger than current
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
            deque.pollLast();
        }
        // add current number from last
        deque.addLast(i);
        // add to result when window size reach k
        if (i >= k - 1) {
            // everything in deque are large elements. The first is always the max since the deque is monotonic.
            res[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return res;
}
```

#### [Find all minimum values of sub-matrices size k](https://leetcode.com/discuss/interview-question/700381/Google-or-Onsite-or-Given-a-matrix-find-all-minimum-values-of-sub-matrices-size-k)

> given an n x m matrix and a value k, find minimum values for all sub-matrixes of size k
>
> example:\
> given this matrix:
>
> ```
> 	[
>         [-1, 5, 4, 1, -3],
>         [4,  3, 1, 1, 6],
>         [2, -2, 5, 3, 1],
>         [8,  5, 1, 9, -4],
>         [12, 3, 5, 8, 1]
>     ]
> ```
>
> and a k of `3`
>
> result:
>
> ```
> [
> 	[-2, -2, -3],
> 	[-2, -2, -4],
> 	[-2, -2, -4]
> ]
> ```

**First for each column calculate the minimum for each sliding window(vertical direction) of k**

**Then for each pair of row having col width k, run sliding window (horizontal direction) of k on col data from 1.**

#### [1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit](https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/)

Similar as the question above. It needs to calculate the difference of an interval. Two deque is needed to get the min and max of the interval. The last element is always the largest or smallest. That:

* In min deque, when the last element is larger than current element, poll last
* in max deque, when the last element is smaller than current element, poll last
* when the element reach to the current element, pop first

As well as maintain the longest interval.&#x20;

```java
public int longestSubarray(int[] nums, int limit) {
    Deque<Integer> minD = new LinkedList<>();
    Deque<Integer> maxD = new LinkedList<>();
    int res = Integer.MIN_VALUE;
    int i = 0, j;
    for (j = 0; j < nums.length; j++) {
        while (!minD.isEmpty() && nums[j] < minD.peekLast()) {
            minD.pollLast();
        }
        while (!maxD.isEmpty() && nums[j] > maxD.peekLast()) {
            maxD.pollLast();
        }
        minD.add(nums[j]);
        maxD.add(nums[j]);
        if (Math.abs(minD.peek() - maxD.peek()) > limit) {
            if (minD.peek() == nums[i]) minD.poll();
            if (maxD.peek() == nums[i]) maxD.poll();
            i++;
        }
    }
    return j - i;
}
```

#### [84. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)

Maintain an increasing monotonic stack. Add a `-1` to the stack for easier calculation. When encounter a decreasing element, pop the stack and calculate the max before current element. At the end, clear all elements in the stack and calculate the left over areas.

```java
public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    int max = 0;
    for (int i = 0; i < n; i++) {
        while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
            max = Math.max(max,
                           heights[stack.pop()] * (i - stack.peek() - 1));
        }
        stack.add(i);
    }
    while (stack.peek() != -1) {
        max = Math.max(max,
                       heights[stack.pop()] * (n - stack.peek() - 1));
    }
    return max;
}
```

#### [901. Online Stock Span](https://leetcode.com/problems/online-stock-span/)

Use a stack and only keep the elements larger than the new element, as well as aggregate the counts less or equals to the new element.&#x20;

```java
class StockSpanner {
    Stack<int[]> stack;
    public StockSpanner() {
        stack = new Stack<>();
    }
    
    public int next(int price) {
        int count = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            count += stack.pop()[1];
        }
        stack.add(new int[]{price, count});
        return count;
    }
}
```

#### [227. Basic Calculator II](https://leetcode.com/problems/basic-calculator-ii/)

Use a stack to store previous numbers. Use an `operator` character to store the last operator. When meet new operator or reach the last digit, perform the operation, aggregate results at last.&#x20;

{% tabs %}
{% tab title="Java" %}

```java
public int calculate(String s) {
    Stack<Integer> stack = new Stack<>();
    int num = 0;
    char operator = '+';
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c >= '0' && c <= '9') {
            num = num * 10 + (c - '0');
        } 
        if ("+-/*".indexOf(c) != -1 || i == s.length() - 1) {
            if (operator == '+') {
                stack.add(num);
            } else if (operator == '-') {
                stack.add(num * -1);
            } else if (operator == '*') {
                stack.add(stack.pop() * num);
            } else if (operator == '/') {
                stack.add(stack.pop() / num);
            }
            num = 0;
            operator = c;
        }
    }
    int res = 0;
    while (!stack.isEmpty()) res += stack.pop();
    return res;
}
```

{% endtab %}

{% tab title="Python" %}

```python
def calculate(self, s: str) -> int:
    stack = []
    op = '+'
    val = 0
    for i in range(len(s)):
        c = s[i]
        if c.isdigit():
            val = val * 10 + int(c)
        if c == '+' or c == '-' or c == '*' or c == '/' or i == len(s) - 1:
            if op == '+':
                stack.append(val)
            elif op == '-':
                stack.append(-val)
            elif op == '*':
                stack.append(val * stack.pop())
            elif op == '/':
                stack.append(int(stack.pop() / val))
            val = 0
            op = c
    res = 0
    for n in stack:
        res += n
    return res
```

{% endtab %}
{% endtabs %}

#### [224. Basic Calculator](https://leetcode.com/problems/basic-calculator/)

```java
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int num = 0, res = 0, sign = 1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                num = num * 10 + (c - '0');
            } else if (c == '+') {
                res += sign * num;
                sign = 1;
                num = 0;
            } else if (c == '-') {
                res += sign * num;
                sign = -1;
                num = 0;
            } else if (c == '(') {
                stack.add(res);
                stack.add(sign);
                res = 0;
                sign = 1;
            } else if (c == ')' && stack.size() > 1) {
                res += sign * num;
                num = 0;
                res *= stack.pop();
                res += stack.pop();
            }
        }
        res += sign * num;
        return res;
    }
```

#### [772. Basic Calculator III](https://leetcode.com/problems/basic-calculator-iii/)

```java
    public int calculate(String s) {
        Queue<Character> q = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c != ' ') {
                q.offer(c);
            }
        }

        q.offer(' '); // placeholder
        return helper(q);
    }

    private int helper(Queue<Character> q) {
        int val = 0;
        int prev = 0, res = 0;
        char prevOp = '+';

        while (!q.isEmpty()) {
            char c = q.poll();

            if (c >= '0' && c <= '9') {
                val = val * 10 + c - '0';
            } else if (c == '(') {
                val = helper(q);
            } else {
                switch (prevOp) { // Note: prevOp, not current c
                    case '+':
                        res += prev;
                        prev = val;
                        break;
                    case '-':
                        res += prev;
                        prev = -val;
                        break;
                    case '*':
                        prev *= val;
                        break;
                    case '/':
                        prev /= val;
                        break;
                }

                if (c == ')') break;

                val = 0;
                prevOp = c;
            }
        }

        return res + prev;
    }
```

#### [726. Number of Atoms](https://leetcode.com/problems/number-of-atoms/)

Store map: element : count to stack. When meeting brackets, deal with the maps in stack. Otherwise, store elements and their count to map.

```java
public String countOfAtoms(String s) {
    Stack<Map<String, Integer>> stack = new Stack<>();
    Map<String, Integer> map = new HashMap<>();
    int i = 0, n = s.length();
    while (i < n) {
        char c = s.charAt(i);
        i++;
        if (c == '(') {
            stack.push(map);
            map = new HashMap<>();
        } else if (c == ')') {
            int val = 0;
            while (i < n && Character.isDigit(s.charAt(i))) {
                val = val * 10 + (s.charAt(i++) - '0');
            }
            if (val == 0) val = 1;
            if (!stack.isEmpty()) {
                Map<String, Integer> temp = map;
                map = stack.pop();
                for (String key : temp.keySet()) {
                    map.put(key, map.getOrDefault(key, 0) + temp.get(key) * val);
                }
            }
        } else {
            int start = i - 1;
            while (i < n && Character.isLowerCase(s.charAt(i))) {
                i++;
            }
            String curt = s.substring(start, i);
            int val = 0;
            while (i < n && Character.isDigit(s.charAt(i))) {
                val = val * 10 + (s.charAt(i++) - '0');
            }
            if (val == 0) val = 1;
            map.put(curt, map.getOrDefault(curt, 0) + val);
        }
    }
    StringBuilder sb = new StringBuilder();
    List<String> list= new ArrayList<>(map.keySet());
    Collections.sort(list);
    for(String key: list){
        sb.append(key);
        if(map.get(key)>1) sb.append(map.get(key));
    }
    return sb.toString();
}
```

Constrained Subsequence Sum

#### [1130. Minimum Cost Tree From Leaf Values](https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/)

Find the smallest consecutive two values to merge to get min cost. When encounter a number is larger than peek, calculate the product of peek (smaller number) and n or the one before peek. Later cumulate all products.

```java
public int mctFromLeafValues(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int res = 0;
    Stack<Integer> stack = new Stack<>();
    for (int n : arr) {
        while (!stack.isEmpty() && n >= stack.peek()) {
            int mid = stack.pop();
            if (stack.isEmpty()) {
                res += mid * n;
            } else {
                res += mid * Math.min(stack.peek(), n);
            }
        }
        stack.add(n);
    }
    while (stack.size() >= 2) {
        res += stack.pop() * stack.peek();
    }
    return res;
}
```

#### [1190. Reverse Substrings Between Each Pair of Parentheses](https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/)

```java
public String reverseParentheses(String s) {
    if(s.length() == 0) return "";
    
    int begin = 0, end = 0;
    for(int i = 0; i < s.length(); i++){
        if(s.charAt(i) == '(') begin = i;
        if(s.charAt(i) == ')') {
            end = i;
            StringBuilder sb = new StringBuilder(s.substring(begin+1, end));
            return reverseParentheses(s.substring(0, begin) + sb.reverse().toString() + s.substring(end+1));
        }
    }
    return s;
}
```

#### [1047. Remove All Adjacent Duplicates In String](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/)

```java
public String removeDuplicates(String S) {
    Stack<Character> stack = new Stack<>();
    for (char c : S.toCharArray()) {
        if (!stack.isEmpty() 
            && stack.peek() == c) {
            stack.pop();
        } else {
            stack.add(c);
        }
    }
    StringBuilder sb = new StringBuilder();
    for (char c : stack) {
        sb.append(c);
    }
    return sb.toString();
}
```

#### [1209. Remove All Adjacent Duplicates in String II](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/)

Save the consecutive character lengths in a stack. When see the same char, and char length equals to k, remove the substring.

```java
public String removeDuplicates(String s, int k) {
    Stack<Integer> stack = new Stack<>();
    StringBuilder sb = new StringBuilder(s);
    for (int i = 0; i < sb.length(); i++) {
        if (i == 0 || sb.charAt(i) != sb.charAt(i - 1)) { // new char
            stack.push(1);
        } else { // same char
            int incre = stack.pop() + 1;
            if (incre == k) {
                sb.delete(i - k + 1, i + 1);
                i -= k;
            } else {
                stack.add(incre);
            }
        }
    }
    return sb.toString();
}
```

Sum of Subarray Minimums

Online Stock Span

Score of Parentheses

Next Greater Element II

Next Greater Element I

Largest Rectangle in Histogram

Trapping Rain Water

Max Value of Equation

#### [946. Validate Stack Sequences](https://leetcode.com/problems/validate-stack-sequences/)

Simulate the stack push and pop operations, validate the sequence in `popped` array and `pop` in the stack.

```java
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed == null || popped == null || pushed.length != popped.length) {
            return false;
        }
        int j = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return j == popped.length;
    }
```

[2334. Subarray With Elements Greater Than Varying Threshold](https://leetcode.com/problems/subarray-with-elements-greater-than-varying-threshold/)

Use monotonic stack to find the last smaller element to the left and right, hence get a range of all elements greater than current:

```java
public int validSubarraySize(int[] nums, int threshold) {
    int n = nums.length;
    Stack<Integer> stack = new Stack<>();
    int[] nextS = new int[n];
    int[] prevS = new int[n];
    Arrays.fill(nextS, n);
    Arrays.fill(prevS, -1);

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
            nextS[stack.peek()] = i;
            stack.pop();
        }
        stack.add(i);
    }

    stack.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
            prevS[stack.peek()] = i;
            stack.pop();
        }
        stack.add(i);
    }

    for (int i = 0; i < n; i++) {
        int left = prevS[i];
        int right = nextS[i] == -1 ? n : nextS[i];
        int len = right - left - 1;
        if ((long)nums[i] * len > threshold) return len;
    }
    return -1;
}
```