网站建设相关的博客有哪些/廊坊seo关键词优化
第三题，300分，单调栈的考点。
天然货仓
题目描述
有一个天然形成的大坑，为台阶状结构，每个台阶的长度都为1,每个都的值为整数(正整数表示高于地平面，零表示与地平面平齐，负整数表示低于地平面)。有一批同等规格的货品(长度为N,高度为1)，货品只能平故，且货物的上表面不能招过地平面(保度为零) ,或者说，高于地平面的地中也不可存故货物。计算一个给定的大坑中最多可以放多少个货品?
输入描述
第一行（物品的宽度）
第二行（坑的宽度）
第三行（坑的深度）的数组
输出描述
给定的大坑中最多可以放的货品数
样例1
输入
2
4
0,-1,-2,0
输出
1
图片自己按照数组画吧，这里就不画了。
样例2
输入
3
8
0,-1,-2,2,1,1,1,2
输出
0
思路分析
这道题考察了单调栈，在leetcode中相似的经典单调栈问题是：42. 接雨水，不过接雨水的水的宽度是1，这个货物的宽度是不定的。
这里默认两边是地平面，可以新建个数组，两端加上0。然后构造单调栈，把索引加入单调栈中，一直维持一个元素逐渐递减的索引单调栈。然后当栈顶为负数，且当前遍历的元素比栈顶元素要大，此时要弹栈，同时计算结果：
- 首先要计算可以装下的最大宽度，计算下边界。
- 然后计算可以装几层，因为可能不只装一层，比如[0,-2,-2,0]在-2为下边界的时候就可以装两层。
参考代码
import java.util.*;public class huocang { // 天然货仓public static void main(String[] args) {Scanner in = new Scanner(System.in);int len = in.nextInt();int n = in.nextInt();in.nextLine();String[] str = in.nextLine().split(",");int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = Integer.parseInt(str[i]);}// 新的数组，默认两边为地平面，即0,数组两端各加一个0int[] nums = new int[arr.length + 2];// 复制原数组的从第0位到length - 1，到新数组的第1位到length，长度为length,两端默认是0System.arraycopy(arr, 0, nums, 1, arr.length);// 单调栈存下标Stack<Integer> stack = new Stack<>();int res = 0;for (int i = 0; i < nums.length; i++) {//当栈顶为负数，且当前遍历的元素比栈顶元素要大，此时要弹栈while (!stack.isEmpty() && nums[stack.peek()] < 0 && nums[i] > nums[stack.peek()]) {int midIndex = stack.pop();int midHeight = nums[midIndex];if (stack.isEmpty())break;int leftIndex = stack.peek(), leftHeight = nums[leftIndex];// i - leftIndex - 1代表的是以midHeight为下界，可以装下的最大宽度// (Math.min(leftHeight, nums[i]) - midHeight)代表的是可以装几层，因为可能不只装一层res += (i - leftIndex - 1) / len * (Math.min(leftHeight, nums[i]) - midHeight);}stack.push(i);}System.out.println(res);}
}
参考了一个大佬的代码，非常值得学习。