leetcode题解-496-下一个更大元素Ⅰ

发表于

题目

官方解way

最大单调递增栈

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
28
29
30
31
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> map;
        stack<int> s;

        for (int i = 0; i < nums2.size(); ++i)
        {
            while (!s.empty() && s.top() < nums2[i])
            {
                map[s.top()] = nums2[i];
                s.pop();
            }
            s.push(nums2[i]);
        }

        while (!s.empty())
        {
            map[s.top()] = -1;
            s.pop();
        }

        vector<int> vi;
        for (int i = 0; i < nums1.size(); ++i)
        {
            vi.push_back(map[nums1[i]]);
        }

        return vi;
    }
};

最大单调递增栈的流程：

数组中元素依次进栈:

  1. 假如栈不为空 且 栈顶元素小于数组当前元素, 则将 栈顶元素出栈 直至 栈不为空 或 栈顶元素 大于等于 数组当前元素
    • 将栈顶元素和第一个大于栈顶(的栈顶右边)元素，形成一个tuple
    • 此处是放到unordered_map中来
  2. 当前元素进栈
  3. 当数组中所有元素遍历完之后，将栈中元素依次弹出
  4. 遍历存放tuple的容器

总结

这是一个很经典的单调栈题。

Reference

https://leetcode-cn.com/problems/next-greater-element-i/solution/xia-yi-ge-geng-da-yuan-su-i-by-leetcode/