王中阳Go

V1

2023/01/17阅读:9主题:橙心

用「单调栈」解决「攒青豆」的实际问题

今天我们来学习下如何应用单调栈的知识点来解决实际问题。

问题描述

攒青豆

现有 n 个宽度为 1 的柱子,给出 n 个非负整数依次表示柱子的高度,排列后如下图所示,此时均匀从上空向下撒青豆,计算按此排列的柱子能接住多少青豆。(不考虑边角堆积)

输入格式

输入每根柱子高度的数组

输出格式

输出一个整数,表示最大能接住多少青豆

输入样例:

[5,0,2,1,4,0,1,0,3]

输出样例:

17

解题思路

通过单调栈找到每根柱子左边第一个比它高的位置,把两根柱子之间的青豆数累加起来,栈内元素是成递减的顺序保存的。

  1. 首先比较当前栈顶元素是否小于当前柱子高度,如果小于栈顶就继续入栈,否则就要找到把栈弹出到第一个比当前柱子高的位置,栈内元素存的数组下标位置,所以可以通过当前下标值与之前的值相减得到宽度差

  2. 使用Last变量记录上一个弹出栈顶的元素高度,因为可以计算两个柱子之间的高度差,每次弹出柱子都要更新一次Last

  3. 最后判断栈是否为空,不空的话需要加上左边柱子比当前柱子高的之间大小

相关代码

import java.util.*;
public class Main{
    public static void main(String[] args){
        int[] height = new int[]{5,0,2,1,4,0,1,0,3};
        System.out.println(qingdou(height));
    }
    static int qingdou(int[] w){
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        //单调栈
        for(int i = 0; i < w.length; i++){            
            int last = 0//上一个栈顶元素
            while(!stack.empty() && w[stack.peek()] <= w[i]){
                res += (w[stack.peek()] - last) * (i - stack.peek() - 1);
                last = w[stack.peek()];
                stack.pop();
            }
            if(!stack.empty()) {
                res += (w[i] - last) * (i - stack.peek() - 1);
            }
            stack.push(i);
        }
        return res;
    }
}

运行效果

在线运行

访问下方链接可以直接在线运行:

https://1024code.com/codecubes/KzFluKB

总结

今天主要分享了对攒青豆的题目理解,有错误的地方欢迎大家指出,共同进步!!

一起写作

YYQQ在加入知识星球后除了一起学Go,坚持学习打卡,也和我一样在坚持写作。

最近参加了字节跳动的青训营活动,在坚持输出。

对写作感兴趣的朋友,可以阅读我之前分享的:写作的“收益”超乎想象

独行难,众行易。我们搞了「坚持周更写作小分队」,欢迎大家加入我们。

规则也非常简单:坚持每周更文一篇即可,虽说多多益善,但是我们更鼓励长久的坚持。

添加微信,备注:写作

原文信息

作者:YYQQ
链接:https://juejin.cn/post/7188897098291478588
来源:稀土掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

分类:

后端

标签:

后端

作者介绍

王中阳Go
V1

专注Go语言开发