建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
用「單調(diào)?！菇鉀Q“攢青豆”這類現(xiàn)實(shí)生活問題
問題描述
攢青豆
現(xiàn)有 n 個寬度為 1 的柱子，給出 n 個非負(fù)整數(shù)依次表示柱子的高度，排列后如下圖所示，此時均勻從上空向下撒青豆，計(jì)算按此排列的柱子能接住多少青豆。（不考慮邊角堆積）
輸入格式
輸入每根柱子高度的數(shù)組
輸出格式
輸出一個整數(shù)，表示最大能接住多少青豆
輸入樣例：
[5,0,2,1,4,0,1,0,3]
輸出樣例：
17
解題思路
通過單調(diào)棧找到每根柱子左邊第一個比它高的位置，把兩根柱子之間的青豆數(shù)累加起來，棧內(nèi)元素是成遞減的順序保存的。
- 首先比較當(dāng)前棧頂元素是否小于當(dāng)前柱子高度，如果小于棧頂就繼續(xù)入棧，否則就要找到把棧彈出到第一個比當(dāng)前柱子高的位置，棧內(nèi)元素存的數(shù)組下標(biāo)位置，所以可以通過當(dāng)前下標(biāo)值與之前的值相減得到寬度差
- 使用Last變量記錄上一個彈出棧頂?shù)脑?strong>高度，因?yàn)榭梢杂?jì)算兩個柱子之間的高度差，每次彈出柱子都要更新一次Last
- 最后判斷棧是否為空，不空的話需要加上左邊柱子比當(dāng)前柱子高的之間大小
相關(guān)代碼
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){
Stackstack = new Stack<>();
int res = 0;
//單調(diào)棧
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;
}
}
運(yùn)行效果
在線運(yùn)行
訪問下方鏈接可以直接在線運(yùn)行：https://1024code.com/codecubes/KzFluKB
總結(jié)
今天主要分享了對攢青豆的題目理解，有錯誤的地方歡迎大家指出，共同進(jìn)步！！
本文轉(zhuǎn)載自微信公眾號「 程序員升級打怪之旅」，作者「王中陽Go」，可以通過以下二維碼關(guān)注。
轉(zhuǎn)載本文請聯(lián)系「 程序員升級打怪之旅」公眾號。
網(wǎng)站名稱：用「單調(diào)棧」解決“攢青豆”這類現(xiàn)實(shí)生活問題
標(biāo)題鏈接：http://www.5511xx.com/article/djcjdcj.html
