查看“Monotonic stack”的源代码

[[Category:刷题]]
单调栈。用于处理 Next Greater Element 这类问题。

== 相关题目 ==

=== [https://leetcode.com/problems/next-greater-element-i/ LeetCode 496. Next Greater Element I] ===

<syntaxhighlight lang=cpp>
vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> res(nums.size()); // 存放答案的数组
    stack<int> s;
    // 倒着往栈里放
    for (int i = nums.size() - 1; i >= 0; i--) {
        // 判定个子高矮
        while (!s.empty() && s.top() <= nums[i]) {
            // 矮个起开，反正也被挡着了。。。
            s.pop();
        }
        // nums[i] 身后的 next great number
        res[i] = s.empty() ? -1 : s.top();
        // 
        s.push(nums[i]);
    }
    return res;
}
</syntaxhighlight>

=== [https://leetcode.com/problems/daily-temperatures/ LeetCode 739. Daily Temperatures] ===

变种，需要返回和 next greater element 之间的距离。

<syntaxhighlight lang=python>
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    ret = [0 for _ in range(len(temperatures))]
    stack = []
    for i in reversed(range(len(temperatures))):
        while stack and temperatures[stack[-1]] <= temperatures[i]:
            stack.pop()
        ret[i] = 0 if not stack else stack[-1] - i
        stack.append(i)
    return ret
</syntaxhighlight>

== 另见 ==

* [https://github.com/labuladong/fucking-algorithm/blob/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%B3%BB%E5%88%97/%E5%8D%95%E8%B0%83%E6%A0%88.md labuladong 的算法小抄中的讲解]