华为2022.4.6笔试第3题单调栈改编

// 高度全是正数的柱子n个，m是货物的长度，货物的高度是1，请问在柱子覆盖的空间中
// 最多放几个货物
// 样例
// 2 6
// 2 4 4 2 4 4
public class S2 {
    public static void main(String[] args) {
        int m,n;
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        int[] h = new int[n+10];
        for (int i=1;i<=n;i++){
            h[i] = sc.nextInt();
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        stack.push(1);
        int ans = 0;
        for (int i=2;i<=n+1;i++){
            while (stack.size()>1 && h[i]<h[stack.peek()]){
                int index = stack.pop();
                int lastindex = stack.peek();
                int maxh = Math.max(h[lastindex],h[i]);
                int heightdiff = h[index] - maxh;
                int l = i - lastindex -1 ;
                ans+= (l/m)*(heightdiff);
            }
            stack.add(i);
        }
        System.out.println(ans);
    }
}