华为机试2022.4.6：天然货仓

第三题，300分，单调栈的考点。

有一个天然形成的大坑，为台阶状结构，每个台阶的长度都为1,每个都的值为整数(正整数表示高于地平面，零表示与地平面平齐，负整数表示低于地平面)。有一批同等规格的货品(长度为N,高度为1)，货品只能平故，且货物的上表面不能招过地平面(保度为零) ,或者说，高于地平面的地中也不可存故货物。计算一个给定的大坑中最多可以放多少个货品?

第一行（物品的宽度）

第二行（坑的宽度）

第三行（坑的深度）的数组

给定的大坑中最多可以放的货品数

2 
4 
0,-1,-2,0

1

图片自己按照数组画吧，这里就不画了。

3
8
0,-1,-2,2,1,1,1,2

0

这道题考察了单调栈，在leetcode中相似的经典单调栈问题是：42. 接雨水，不过接雨水的水的宽度是1，这个货物的宽度是不定的。

这里默认两边是地平面，可以新建个数组，两端加上0。然后构造单调栈，把索引加入单调栈中，一直维持一个元素逐渐递减的索引单调栈。然后当栈顶为负数，且当前遍历的元素比栈顶元素要大，此时要弹栈，同时计算结果：

1. 首先要计算可以装下的最大宽度，计算下边界。
2. 然后计算可以装几层，因为可能不只装一层，比如[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,数组两端各加一个0
        int[] nums = new int[arr.length + 2];
        // 复制原数组的从第0位到length - 1，到新数组的第1位到length，长度为length,两端默认是0
        System.arraycopy(arr, 0, nums, 1, arr.length);

        // 单调栈存下标
        Stack 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);
    }
}

参考了一个大佬的代码，非常值得学习。