大厂算法面试之 leetcode 精讲 13. 单调栈
大厂算法面试之 leetcode 精讲 13.单调栈
视频讲解(高效学习):点击学习
目录:
239. 滑动窗口最大值 (hard)
方法 1.优先队列
思路:最大值问题我们可以采用大顶堆,具体就是维护一个大顶堆,初始的时候将
0~k-1
的元素加入堆中,存入的是值和索引的键值队,然后滑动窗口从从索引为 k 的元素开始遍历,将新进入滑动窗口的元素加堆中,当堆顶元素不在滑动窗口中的时候,不断删除堆顶堆元素,直到最大值在滑动窗口里。复杂度分析:时间复杂度
O(nlogn)
,n 是 nums 的长度,将一个元素加入优先队列的时间复杂度是 logn,最坏的情况下所有元素都要入队,所以复杂度是 nlogn。空间复杂度是O(n)
,最坏的情况下,所有元素都在队列中,所以是O(n)
js:
java:
方法 2.单调队列
思路:维护单调递减队列,当进入滑动窗口的元素大于等于队尾的元素时 不断从队尾出队,直到进入滑动窗口的元素小于队尾的元素,才可以入队,以保证单调递减的性质,当队头元素已经在滑动窗口外了,移除对头元素,当 i 大于等于 k-1 的时候,单调递减队头就是滑动窗口的最大值
复杂度分析:时间复杂度
O(n)
,n 是 nums 的长度,每个元素入队一次。空间复杂度O(k)
,队列最多存放 k 大小的元素
js:
Java:
84. 柱状图中最大的矩形 (hard)
思路:准备单调递增栈存放数组下标,因为这样可以从栈顶找到左边第一个比自己小的下标,这样从当前下标出发到第一个比自己小的柱子的下标就是矩形面积的宽度,然后在乘当前柱子的高度就是面积,如果当前柱子大于栈顶的下标对应的柱子高度,就入栈,否则不断出栈,计算栈顶的柱子所能形成的矩形面积,然后更新最大矩形面积
复杂度:时间复杂度
O(n)
,n 是 heights 的长度,数组里每个元素尽出栈一次。空间复杂度O(n)
,栈空间最多为 n
js:
java:
85. 最大矩形 (hard)
方法 1.单调栈
思路:84 题的变种,从第一行到第 n 行形成的柱状图可以利用 84 题求解,然后循环每一行,计算以这一行为底的柱状图最大面积,然后更新最大矩形面积
复杂度:时间复杂度
O(mn)
,m、n 分别是矩形的高度和宽度,循环 m 次行,每行里循环每个柱子的高度。空间复杂度O(n)
,heights 数组的空间。
js:
java:
496. 下一个更大元素 I (easy)
思路:
循环 nums2,如果循环的元素大于栈顶元素,并且栈不为空,则不断将栈顶元素作为 key,当前元素作为 value 加入 map 中
本质是第一个比栈顶元素大的值会让栈中的元素不断出队 所以这个数就是这些出栈元素的下一个更大的数
剩下来的元素就是没有找到最大值的
遍历 nums1 将结果推入 ans 中
复杂度:时间复杂度
O(m+n)
,nums1、nums2 遍历一遍,nums2 中的元素入队出队一次。空间复杂度O(n)
,栈空间和 map 的空间的复杂度
js:
java:
42. 接雨水 (hard)
思路:首先考虑暴力做法,找找思路,暴力做法可以遍历数组,在每个位置分别往两边寻找左柱子中的最大高度和右柱子中的最大高度,找到之后,用左右最大高度的较小者减去当前柱子的高度,就是当前位置能接的水量。该方法要循环整个数组,并且每个位置要遍历数组寻找左右柱子高度的最大值,嵌套了一层循环,所以复杂度是
O(n^2)
。我们怎样加速嵌套的这层循环呢,其实可以预先计算从左往右和从右往左的最大高度数组,在循环数组的时候,可以直接拿到该位置左右两边的最大高度,当前位置的接水量就是左右两边高度的较小者减去当前位置柱子的高度
复杂度:时间复杂度
O(n)
,寻找左右的最大高度,循环计算每个位置的接水量,总共 3 个循环,但他们不是嵌套关系。空间复杂度是O(n)
,n 是heights
数组,用到了leftMax
和rightMax
数组,即存放左右两边最大高度的数组。
方法 1.动态规划
js:
java:
方法 2:单调栈
思路:遍历
heights
数组,将其中的元素加入单调递减栈,如果当前柱子的高度大于栈顶柱子的高度, 不断出栈,相当于找到左边比当前柱子矮的位置,然后每次出栈之后都要累加一下面积。复杂度:时间复杂度
O(n)
,n 是 heights 的长度,数组中的每个元素最多入栈出栈一次。空间复杂度O(n)
,栈的空间,最多不会超过heights
的长度
js:
java:
方法 3.双指针
思路:如果右边存在一个比当前高的柱子,就会形成一个洼地,同理,左边存在一个比当前高柱子,也会形成一个坑,用双指针循环
heights
数组,判断是否形成洼地,如果能形成洼地,则计算积水量,累加进 ans。复杂度:时间复杂度
O(n)
,n 为heights
的长度, 总共遍历heights
一次。空间复杂度O(1)
,只用到了两个指针
js:
java:
评论