用「單調棧」解決“攢青豆”這類現實生活問題

作者：YYQQ&王中陽 2023-02-13 07:53:33

開發前端

現有 n 個寬度為 1 的柱子，給出 n 個非負整數依次表示柱子的高度，排列后如下圖所示，此時均勻從上空向下撒青豆，計算按此排列的柱子能接住多少青豆。（不考慮邊角堆積）。

問題描述

攢青豆

現有 n 個寬度為 1 的柱子，給出 n 個非負整數依次表示柱子的高度，排列后如下圖所示，此時均勻從上空向下撒青豆，計算按此排列的柱子能接住多少青豆。（不考慮邊角堆積）

輸入格式

輸入每根柱子高度的數組

輸出格式

輸出一個整數，表示最大能接住多少青豆

輸入樣例：

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

輸出樣例：

解題思路

通過單調棧找到每根柱子左邊第一個比它高的位置，把兩根柱子之間的青豆數累加起來，棧內元素是成遞減的順序保存的。

首先比較當前棧頂元素是否小于當前柱子高度，如果小于棧頂就繼續入棧，否則就要找到把棧彈出到第一個比當前柱子高的位置，棧內元素存的數組下標位置，所以可以通過當前下標值與之前的值相減得到寬度差
使用Last變量記錄上一個彈出棧頂的元素高度，因為可以計算兩個柱子之間的高度差，每次彈出柱子都要更新一次Last
最后判斷棧是否為空，不空的話需要加上左邊柱子比當前柱子高的之間大小

相關代碼

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

總結

今天主要分享了對攢青豆的題目理解，有錯誤的地方歡迎大家指出，共同進步！！

本文轉載自微信公眾號「程序員升級打怪之旅」，作者「王中陽Go」，可以通過以下二維碼關注。

轉載本文請聯系「程序員升級打怪之旅」公眾號。

責任編輯：武曉燕來源：程序員升職加薪之旅

單調棧柱子非負整數