ARTICLE DETAIL

资讯详情

深耕网站建设、视觉设计与SEO优化的一线实战洞察。

重练算法(代码随想录版) day48 - 单调栈part1

重练算法(代码随想录版) day48 - 单调栈part1

今日刷题量:3
当前刷题总量:171
Easy: 63
Mid: 98
Hard: 10

Day48
解题思想
单调栈的本质:维护一个“单调递减栈(存下标)”,当前元素比栈顶大时,说明它就是栈顶元素的「下一个更大值」
核心动作:

  • while 栈不空 && 当前值 > 栈顶对应的值:
    ** 栈顶的 nextGreater = 当前值(或索引差)
    ** 弹栈
  • 当前元素入栈

单调栈模版:

点击查看代码
stack<int> st;        // 存下标
vector<int> ans(n, 默认值);for (int i = 0; i < 遍历范围; i++) {int idx = i % n;  // 是否循环,看题目while (!st.empty() && nums[idx] > nums[st.top()]) {ans[st.top()] = ...;   // 填答案st.pop();}st.push(idx);     // 是否 push,看题目
}

练习题目
739. 每日温度(mid):https://leetcode.cn/problems/daily-temperatures/
496.下一个更大元素 I (easy):https://leetcode.cn/problems/next-greater-element-i/description/
503.下一个更大元素II (mid):https://leetcode.cn/problems/next-greater-element-ii/description/

返回列表