記錄力扣每日一題
題目鏈接
題目描述:
給定一個直方圖(也稱柱狀圖)，假設有人從上面源源不斷地倒水，最后直方圖能存多少水量?直方圖的寬度為 1，
上面是由陣列 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方圖，在這種情況下，可以接 6 個單位的水（藍色部分表示水）
示例:
輸入: [0,1,0,2,1,0,1,3,2,1,2,1]
輸出: 6
思路:
左右視圖,同一位置取較小值, 便是當前位置能夠儲水的最大高度, 最后在減去構成容器的直方圖的高度,就是最終儲水的結果
int trap(vector<int>& height) {
// 從左向右得到直方圖的左視圖, 在得到右視圖, 每個位置取較小值
int res = 0;
if(height.empty())
return res;
vector<int> left(height.size(), 0);
vector<int> right(height.size(), 0);
int lmax, rmax = 0;
for(int i = 0; i < height.size(); ++i){
// 從左向右, 得到直方圖的左視圖
left[i] = max(lmax, height[i]);
if(lmax < height[i])
lmax = height[i];
// 從右向左,得到直方圖的右視圖
right[height.size()-1-i] = max(rmax, height[height.size()-1-i]);
if(rmax < height[height.size()-1-i])
rmax = height[height.size()-1-i];
}
for(int i = 0; i < height.size()-1; ++i){
// 取左,右視圖同一位置處, 較小值就是就可以儲水的最高高度, 再減去構成直方圖的值
res += (min(left[i], right[i]) - height[i]);
}
return res;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/271894.html
標籤：其他
上一篇：修改《植物大戰僵尸》游戲資料
下一篇：植物大戰僵尸如何修改金幣和關卡