刷穿剑指offer-Day18-栈II 单调栈的解题思路

简介: 刷穿剑指offer-Day18-栈II 单调栈的解题思路

昨日回顾


昨天我们开启了栈这个数据结构的章节,分别介绍了Python和Java中栈的初始化与使用。然后通过三道题目,对栈的解题和分析有了一个初步的了解。

然而昨天的栈题目,主要是针对题目的条件,判断是否需要弹出栈内元素,属于通用的栈场景。然而,今天需要介绍的是栈中特殊的一类题目,单调栈

既然是单调的,那么要么单调增、要么单调减。当我们遇到一道题目时,如何判断是否该使用单调栈的方法去解题呢?这里要注意,单调栈的题目,最通用的关键字是下一个更大(小)的 等等。

而主要的单调栈思路就是,需要不断根据数组后续的内容,来获得更大、更优的解。

说了这么多,主要是让大家有一个初步的概念,然后在通过后续的题目的分析,深入的理解这类题目的特点。先来看一道比较明显的单调栈问题吧。


剑指OfferII038.每日温度


https://leetcode-cn.com/problems/iIQa4I/solution/shua-chuan-jian-zhi-offer-day18-zhan-ii-mdv06/

难度:中等


题目:

请根据每日 气温 列表 temperatures ,重新生成一个列表,要求其对应位置的输出为: 要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。

提示:

  • 1 <= temperatures.length <= 10 ^ 5
  • 30 <= temperatures[i] <= 100


示例:

示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]


分析

这是一道比较典型的单调栈问题。 根据题意我们需要找到下一个更高的气温,然后计算两者相差的天数。 这里注意,如果气温在这之后都不会升高,则将该位置用0来代替。

  1. 根据以上的信息,我们可以先创建一个temperatures等长的全零数组,然后初始化一个栈
  2. 这里注意由于需要返回相差天数,所以栈中需要保存元素下标来实现天数计算。
  3. 下来循环temperatures进行栈的操作,循环过程中,持续判断当前下标温度与栈顶下标温度的大小差别
  4. 如果当前下标的温度大于栈顶下标的温度,表示找到了下一个更大的温度,弹出栈顶下标,计算天数差别, 更新ret[栈顶下标] = 当前下标 - 栈顶下标
  5. 否则将当前下标加入栈顶
  6. ret中没有更新的元素,表示未找到更高的温度,最终返回ret即可。

这里模拟题目中示例1,给出栈和ret的变化,供大家参考:

  • 输入: temperatures = [73,74,75,71,69,72,76,73]
  • 输出: [1,1,4,2,1,1,0,0]
下标 -> 元素 等待天数 说明
0 -> 73 [73] [0, 0, 0, 0, 0, 0, 0, 0] 0入栈
1 -> 74 [74] [1, 0, 0, 0, 0, 0, 0, 0] 0出栈、1入栈
2 -> 75 [75] [1, 1, 0, 0, 0, 0, 0, 0] 1出栈、2入栈
3 -> 71 [75, 71] [1, 1, 0, 0, 0, 0, 0, 0] 3入栈
4 -> 69 [75, 71, 69] [1, 1, 0, 0, 0, 0, 0, 0] 4入栈
5 -> 72 [75, 72] [1, 1, 0, 2, 1, 0, 0, 0] 3、4出栈,5入栈
6 -> 76 [76] [1, 1, 4, 2, 1, 1, 0, 0] 2、5出栈、6入栈
7 -> 73 [76, 73] [1, 1, 4, 2, 1, 1, 0, 0] 7入栈


解题:


Python:

class Solution:
    def dailyTemperatures(self, temperatures):
        stack, ret = [], [0] * len(temperatures)
        for i, num in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < num:
                index = stack.pop()
                ret[index] = i - index
            stack.append(i)
        return ret


Java:

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int[] ret = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.empty() && temperatures[stack.peek()] < temperatures[i]) {
                int index = stack.pop();
                ret[index] = i - index;
            }
            stack.push(i);
        }
        return ret;
    }
}

有了这道题目作为单调栈思维的入门,相信大家在基本套路上已经有所了解了。下来,我们在做一个同类型、同难度的单调栈问题,检验下大家是否掌握了这种方法。


503.下一个更大元素II


https://leetcode-cn.com/problems/next-greater-element-ii/solution/503xia-yi-ge-geng-da-yuan-su-ii-fen-xi-b-yxb2/

难度:中等


题目:

给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。

数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的

下一个更大的数。如果不存在,则输出 -1。

注意: 输入数组的长度不会超过 10000。


示例:

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2;
数字 2 找不到下一个更大的数; 
第二个 1 的下一个最大的数需要循环搜索,结果也是 2。


分析

做过上一题,根据单调栈计算下标差值的实现,相信想通过这道题也不会有太大难度。由于题目差异不大,在这里就简单分析下吧。

首先我们维护一个ret = [-1] * len(nums)的数组,由于是循环数组,所以我们需要循环两次nums,使用单调栈的方式存储下标。

如果找到比栈顶大的元素,则对栈内存储的下标对应的ret赋值。


解题:


Python:

class Solution:
    def nextGreaterElements(self, nums):
        ln = len(nums)
        ret = [-1] * ln
        stack = []
        for i in range(ln * 2 - 1):
            while stack and nums[stack[-1]] < nums[i % ln]:
                ret[stack.pop()] = nums[i % ln]
            stack.append(i % ln)
        return ret


Java:

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int lg = nums.length;
        int[] ret = new int[lg];
        Arrays.fill(ret, -1);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < lg * 2 - 1; i++) {
            while (!stack.empty() && nums[stack.peek()] < nums[i % lg]){
                ret[stack.pop()] = nums[i % lg];
            }
            stack.push(i % lg);
        }
        return ret;
    }
}


剑指OfferII039.直方图最大矩形面积


https://leetcode-cn.com/problems/0ynMMM/

难度:困难


题目:

给定非负整数数组 heights ,数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

提示:

  • 1 <= heights.length <=105
  • 0 <= heights[i] <= 104


示例:

网络异常,图片无法展示
|

image.png


分析

首先我们需要明确的是,什么时候入栈什么时候出栈?

通过图例我们也可以发现,如果当前元素比栈顶元素大时,我们入栈并继续计算下一个。如果当元素小于栈顶元素时,将位于栈顶的柱子的下标出栈,并且计算以位于栈顶的柱子为顶的最大矩形面积。

那么,如果数组时单调递增的,岂不是一直入栈没有返回了?记得之前我们在数组章节介绍过哨兵节点,所以在单调栈这种求最大值的时候,也需要设置哨兵节点。即设置左右两端点的高度为0,则可以在初始计算及最终结果时,能够完整计算所有面积。

如果还不明确,可以按照温度那道题,创建一个表格填写一下每一步的操作过程,会更利于大家去学习。

最终代码如下:


解题:


Python:

class Solution:
    def largestRectangleArea(self, heights):
        stack, ret = [], 0
        heights= [0] + heights + [0]
        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                ret = max(ret, h * (i - 1 - stack[-1]))
            stack.append(i)
        return ret


Java:

class Solution {
    public int largestRectangleArea(int[] heights) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        int[] new_heights = new int[heights.length + 2];
        for (int i = 1; i < heights.length + 1; i++) {
            new_heights[i] = heights[i - 1];
        }
        for (int i = 0; i < new_heights.length; i++) {
            while (!stack.empty() && new_heights[i] < new_heights[stack.peek()]) {
                int h = new_heights[stack.pop()];
                res = Math.max(res, (i - stack.peek() - 1) * h);
            }
            stack.push(i);
        }
        return res;
    }
}




目录
打赏
0
0
0
0
1
分享
相关文章
|
10天前
|
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
25 11
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
2月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
160 77
|
2月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
48 7
|
2月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
53 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
2月前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
52 9
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
107 5
|
4月前
|
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
77 0
|
4月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
66 1
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
135 21
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等