[Java/C++/Python] One Pass Stack Solution O(n)
Intuition\nNext Greater Element canb resolved with one mono stack.\nCould we resolve this problem with mono stack?\n\n\n# Explanation\nUse two stack s1 and s2.\
# **Intuition**\nNext Greater Element canb resolved with one mono stack.\nCould we resolve this problem with mono stack?\n<br>\n\n# **Explanation**\nUse two stack `s1` and `s2`.\nSimilar to "Next Greater Element"\n`s1` stores the index of elements\nthat have not found their first greater element.\n\n`s2` stores the index of elements\nthat have found their first greater element,\nhave not found their second greater element.\n\nFor each `a = A[i]` in A\nWe first compare the `a` with the tail elements in `s2`,\npop all element smaller than `a`,\nbecause `a` is their second greater element.\n\nThen we compare the `a` with the tail elements in `s1`,\nmove all elements smaller than `a` to the tail of `s2`,\nbecause `a` is their first greater element.\n\nWe repeatly do this for all `A[i]` and finally return the result.\n<br>\n\n# **Complexity**\nAll `A[i]` is pushed in `s1` and `s2` at most once.\nAll `A[i]` is pushed in `s1` and `s2` at most once.\n\nTime `O(n)`\nSpace `O(n)`\n<br>\n\n**Java**\n```java\n    public int[] secondGreaterElement(int[] A) {\n        int n = A.length,  res[] = new int[n];\n        Arrays.fill(res, -1);\n        Stack<Integer> s1 = new Stack<>(), s2 = new Stack<>(), tmp = new Stack<>();\n        for (int i=0; i < n; i++) {\n            while (!s2.empty() && A[s2.peek()] < A[i])\n                res[s2.pop()] = A[i];\n            while (!s1.empty() && A[s1.peek()] < A[i])\n                tmp.push(s1.pop());\n            while (!tmp.empty())\n                s2.push(tmp.pop());\n            s1.push(i);\n        }\n        return res;\n    }\n```\n\n**C++**\n```cpp\n    vector<int> secondGreaterElement(vector<int>& A) {\n        int n = A.size();\n        vector<int> res(n, -1), s1, s2, tmp;\n        for (int i = 0 ;i < n; ++i) {\n            while (!s2.empty() && A[s2.back()] < A[i])\n                res[s2.back()] = A[i], s2.pop_back();\n            while (!s1.empty() && A[s1.back()] < A[i])\n                tmp.push_back(s1.back()), s1.pop_back();\n            while (!tmp.empty())\n                s2.push_back(tmp.back()), tmp.pop_back();\n            s1.push_back(i);\n        }\n        return res;\n    }\n```\n\n**Python**\n```py\n    def secondGreaterElement(self, A: List[int]) -> List[int]:\n        res, s1, s2 = [-1] * len(A), [], []\n        for i,a in enumerate(A):\n            while s2 and A[s2[-1]] < a:\n                res[s2.pop()] = a;\n            tmp = []\n            while s1 and A[s1[-1]] < a:\n                tmp.append(s1.pop())\n            s2 += tmp[::-1]\n            s1.append(i)\n        return res\n```\n\n# More Good Stack Problems\nHere are some problems that impressed me.\nGood luck and have fun.\n\n- 2454. [Next Greater Element IV](https://leetcode.com/problems/next-greater-element-iv/discuss/2756668/JavaC%2B%2BPython-One-Pass-Stack-Solution)\n- 2398. [Maximum Number of Robots Within Budget](https://leetcode.com/problems/maximum-number-of-robots-within-budget/discuss/2524838/Python-Sliding-Window-O(n))\n- 2289. [Steps to Make Array Non-decreasing](https://leetcode.com/problems/steps-to-make-array-non-decreasing/discuss/2085864/)\n- 2281. [Sum of Total Strength of Wizards](https://leetcode.com/problems/sum-of-total-strength-of-wizards/discuss/2061985/python-solution-on/1405190)\n- 1776. [Car Fleet II](https://leetcode.com/problems/car-fleet-ii/discuss/1085987/javacpython-on-stack-solution/)\n- 1673. [Find the Most Competitive Subsequence](https://leetcode.com/problems/find-the-most-competitive-subsequence/discuss/952786/javacpython-one-pass-stack-solution/776191 )\n- 1671. [Minimum Number of Removals to Make Mountain Array](https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array/discuss/952136/Python-LIS-O(nlogn))\n- 1475. [Final Prices With a Special Discount in a Shop](https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop/discuss/685390/javacpython-stack-one-pass/809992)\n- 1425. [Constrained Subsequence Sum](https://leetcode.com/problems/constrained-subsequence-sum/discuss/597751/JavaC++Python-O(N)-Decreasing-Deque)\n- 1130. [Minimum Cost Tree From Leaf Values](https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/discuss/339959/One-Pass-O(N)-Time-and-Space)\n- 907. [Sum of Subarray Minimums](https://leetcode.com/problems/sum-of-subarray-minimums/discuss/170750/C++JavaPython-Stack-Solution)\n- 901. [Online Stock Span](https://leetcode.com/problems/online-stock-span/discuss/168311/C++JavaPython-O(1))\n- 856. [Score of Parentheses](https://leetcode.com/problems/score-of-parentheses/discuss/141777/C++JavaPython-O(1)-Space)\n- 503. [Next Greater Element II](https://leetcode.com/problems/next-greater-element-ii/discuss/98270/JavaC++Python-Loop-Twice)\n- 496. Next Greater Element I\n- 84. Largest Rectangle in Histogram\n- 42. Trapping Rain Water\n<br>\n
['C', 'Python', 'Java']