记录生活中的点点滴滴

0%

单调栈刷题记录总结

今天一直在搞单调栈这个专题,之前也经常碰到,今天干脆刷题然后总结一下,便于后续查看复习!

包含以下的题:

42. 接雨水

84. 柱状图中最大的矩形

11. 盛最多水的容器

901. 股票价格跨度

739. 每日温度

1081. 不同字符的最小子序列

402. 移掉K位数字

581. 最短无序连续子数组

42. 接雨水

其实每一个下标它所能积攒的雨水是其 左边最大 和 右边最大 两个其中较小的,然后减去当前的高度!

就比如第三位高度为0,左边最大为1,右边最大为3,较小的为1,减去当前高度0,结果为1就是当前能积攒的雨水!

所以一种解法就是先声明两个数组,一个求左边最大的,另一个求右边最大的,然后遍历,根据上面的逻辑再计算总的雨水。

代码如下:

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
public int trap(int[] height) {
//对于任意一位,它的高度其实是左边最大值和右边最大值 两者最小值 减去 当前高度
//先声明两个数组,表示左边、右边最大值
int n = height.length;
int[] l = new int[n];
int[] r = new int[n];
int max = -1;
for(int i=0;i<n-1;i++){
max = Math.max(max,height[i]);
l[i] = max;
}
max = -1;
for(int i=n-1;i>=0;i--){
max = Math.max(max,height[i]);
r[i] = max;
}
int sum = 0;
//第一位和最后一位跳过
for(int i=1;i<n-1;i++){
if(Math.min(l[i],r[i])>height[i]){
sum+=Math.min(l[i],r[i])-height[i];
}
}
return sum;
}

还有另外一种方法,利用单调栈,高度迭代入栈,不过入栈的是下标,因为后续要去求距离,然后如果当前的高度比栈顶的高度还要大,说明栈顶那个元素可能有积水,让它出栈,然后根据下一个栈顶元素下标,这些元素去求解!

代码如下:

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
//单调栈求解
public int trap(int[] height) {
int n = height.length;
int curr = 0;//当前下标
Stack<Integer> s = new Stack<>();//存放下标
int res = 0;//结果
while(curr<n){
while(!s.isEmpty() && height[curr]>height[s.peek()]){
int t = height[s.pop()];
//如果s为空,没有左边的,肯定不能继续下去了,所以break
if(s.isEmpty()){
break;
}
//长,等于当前下标再减去下一个栈头的下标
int dis = curr-s.peek()-1;
//高度取最小的值,不过还要减去栈弹出的元素的值即t
int h = Math.min(height[curr],height[s.peek()]);
//结果+=
res += dis*(h-t);
}
//当前下标入栈,然后下标++,进行下一个迭代
s.push(curr++);
}
return res;
}

84. 柱状图中最大的矩形

普通的暴力方法其实就是看看以每一个下标为高度,求解其最大长度,然后长乘高就是面积,怎样求其最大的长度呢?其实左边需要往前遍历到第一个小于当前高度的下标,左边需要往后遍历到第一个小于当前高度的下标!

这样可以解决,但是会超时,我们还需要想一下能不能利用栈去避免每一次都往前后遍历呢!

其实就是利用,当前元素入栈时,要是比栈顶元素高度要小的时候,那么栈顶元素不就是需要出栈了,那么以这个元素为高度的长其实也就确定了,因为我们这个栈是一个递增的栈。

还有一点就是为了避免后续的栈非空,造成我们还要进行其他一些操作时,需要设置哨兵,也就是在数组前后各添加一个0元素,这样遍历完毕之后,本来数组的那些高度都能弹出栈,都能计算完毕!

好的,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int largestRectangleArea(int[] heights) {
// 这里为了代码简便,在柱体数组的头和尾加了两个高度为 0 的柱体。
int[] tmp = new int[heights.length + 2];
System.arraycopy(heights, 0, tmp, 1, heights.length);

Deque<Integer> stack = new ArrayDeque<>();
int area = 0;
for (int i = 0; i < tmp.length; i++) {
// 对栈中柱体来说,栈中的下一个柱体就是其「左边第一个小于自身的柱体」;
// 若当前柱体 i 的高度小于栈顶柱体的高度,说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。
// 因此以栈顶柱体为高的矩形的左右宽度边界就确定了,可以计算面积🌶️ ~
while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {
int h = tmp[stack.pop()];
area = Math.max(area, (i - stack.peek() - 1) * h);
}
stack.push(i);
}
return area;
}

11. 盛最多水的容器

又是图表题,看看咋办。

这道题最粗暴的方法当然是O(n^2),当然对于medium难度的题目来说,显然不能这么做 这道题要解决的问题是,找寻最大的一组(i,j),使得Area最大

1
Area = Max(min(height[i], height[j]) * (j-i)) {其中0 <= i < j < height,size()}

这里用到了动态规划,基本的表达式: area = min(height[i], height[j]) * (j - i) 使用两个指针,值小的指针向内移动,这样就减小了搜索空间 !因为面积取决于指针的距离与值小的值乘积,如果值大的值向内移动,距离一定减小,而求面积的另外一个乘数一定小于等于值小的值,因此面积一定减小,而我们要求最大的面积,因此值大的指针不动,而值小的指针向内移动遍历!

所以利用双指针就能求解出来,代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxArea(int[] height) {
int l = 0;
int r = height.length-1;
int max = 0;
while(l<r){
max = Math.max(max,Math.min(height[l],height[r])*(r-l));
if(height[l]>height[r]){
r--;
}else{
l++;
}
}
return max;
}

用什么方法,我们要根据每道题的要求去想,然后再弄明白它内在的一些逻辑!

901. 股票价格跨度

因为没有了数组,我们可以自己创建一个List,或者使用Pair这个类!

代码如下:还是单调栈的应用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class StockSpanner {
//key:下标 value:值
private Stack<Pair<Integer,Integer>> s;

public StockSpanner() {
s = new Stack<>();
}

public int next(int price) {
int len = s.isEmpty() ? 0 : s.peek().getKey()+1;
while(!s.isEmpty() && s.peek().getValue()<=price){
s.pop();
}
int res = s.isEmpty() ? len+1 : len-s.peek().getKey();
s.push(new Pair<>(len,price));
return res;
}
}

739. 每日温度

还是单调栈,冲:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] dailyTemperatures(int[] T) {
int len = T.length;
int[] res = new int[len];
Stack<Integer> s = new Stack<>();
for(int i=0;i<len;i++){
while(!s.isEmpty() && T[i]>T[s.peek()]){
int t = s.pop();
res[t] = i-t;
}
s.push(i);
}
while(!s.isEmpty()){
res[s.pop()] = 0;
}
return res;
}

1081. 不同字符的最小子序列

利用单调栈,不过有一点需要注意的是,出栈的时候要判断一下从当前节点开始后面的字符中是否含有这个出栈的字符,如果含有才可以出栈,否则不能出栈!

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String smallestSubsequence(String s) {
Stack<Character> stack = new Stack<>();
char[] cs = s.toCharArray();
int n = cs.length;
for(int i=0;i<n;i++){
if(stack.contains(cs[i])){
continue;
}
while(!stack.isEmpty() && cs[i]<stack.peek() && s.indexOf(stack.peek(),i)!=-1){
stack.pop();
}
stack.push(cs[i]);
}
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()){
sb.append(stack.pop());
}
return sb.reverse().toString();
}

402. 移掉K位数字

题目的意思是k限制了出栈的次数,所以出栈的时候还要让k减1,判断出栈的条件还需要添加一个k需要大于0才可以。另外,如果本来就是递增的,一直不会出栈,比如12345,所以还要让k最后等于0,那么此时也要出栈,直到最终k为0或者栈为空,然后根据栈内元素去构造最终的字符串!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public String removeKdigits(String num, int k) {
Deque<Character> s = new ArrayDeque<>();
char[] cs = num.toCharArray();
int n = cs.length;
for(int i=0;i<n;i++){
while(k>0 && !s.isEmpty() && cs[i]<s.peek()){
s.pop();
k--;
}
if(s.isEmpty() && cs[i]=='0')continue;
s.push(cs[i]);
}
while(k>0 && !s.isEmpty()){
s.pop();
k--;
}
StringBuilder res = new StringBuilder();
while(!s.isEmpty()){
res.append(s.poll());
}
return res.length()==0 ? "0" : res.reverse().toString();
}

581. 最短无序连续子数组

其实最简单的一个做法就是:先排序,然后从左边开始比较,找到不同的第一个数,这就是开始,右边从尾开始比较,找到不同的第一个数,这个就是结尾。两者之间的距离就是要的长度!

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int findUnsortedSubarray(int[] nums) {
int n = nums.length;
if (n == 1) return 0;
int[] numsSort = nums.clone();
Arrays.sort(numsSort);
int left = Integer.MAX_VALUE, right = 0;
for (int i=0;i<n;i++) {
if (numsSort[i] != nums[i]) {
left = i;
break;
}
}
for (int i=n-1;i>=0;i--) {
if (numsSort[i] != nums[i]) {
right = i;
break;
}
}
if (right - left >= 0) return right - left + 1;
else return 0;
}

这样需要我们去排序,复杂度就是O(nlogn)。

我们想一想,能不能不排序,就找到左边第一个和右边第一个,先说左边第一个吧!

其实有这么一个做法就可以,我们从右边往前遍历,不断更新min值,就是当前能遇到的最小值,判断当前元素是否和上一个最小元素,如果当前元素大于的话,说明左边第一个就是当前元素下标!不断往前迭代更新左边第一个l的值就可以!其实也可以反过来看,如果数组本来就是升序的,这样每次当前元素都会小于上一个最小的元素。多想一想,就会发现这个办法是可以找到的。

同理,找右边第一个也是这个方法,只不过是从前往后迭代遍历就行了!

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int findUnsortedSubarray(int[] nums) {
int n = nums.length;
int l=n-1,lv=nums[l];
for(int i=n-2;i>=0;i--){
if(nums[i]>lv){
l = i;
}
lv = Math.min(lv,nums[i]);
}
int r=0,rv=nums[r];
for(int i=1;i<n;i++){
if(nums[i]<rv){
r = i;
}
rv = Math.max(rv,nums[i]);
}
return r>l ? r-l+1 : 0;
}

OK,就写到这里吧,今天也就刷了这点题,现在都八点了,再去学习会SpringCloud吧,太混了!