Java ArrayDeque push() 似乎添加到堆栈的 front/tail [潜在错误]

Question

我正在研究 leetcode 问题 84，最大矩形。在测试时，我遇到了这个奇怪的情况，堆栈似乎添加到尾部。我使用打印语句和迭代器对象确认了这一点。

测试用例为：[4,2,0,3,2,5]

数组中的倒数第二个元素 2 似乎被推到了尾部，就在 0 的下方（它应该被推到顶部。在我的打印语句中，val:x gap:y 出现在元素被弹出时， x y z 出现在元素被推入并添加时： x 是迭代器打印的内容。整个堆栈在数组的每个增量处迭代。代码在这里。我确定只是发布了一个像这样的代码块是不礼貌的，所以请随时提出一些批评。

class Solution {
    public int largestRectangleArea(int[] heights) {
        //use a stack
        //if element is bigger than top of stack, than add element to stack
        //if element is same as top, add element to stack
        //if element is less than top, pop all elements and calculate areas, also keep track of area of new top
        
        Deque<Helper> myStack = new ArrayDeque<Helper>();
        
        if (heights.length == 0 || heights == null) return 0;
        if (heights.length == 1) return heights[0];
        
        int poppedLength = 0;
        int area;
        int maxArea = 0;
        Helper previous = new Helper(heights[0]);
        
        myStack.push(previous);
        
        for (int i = 1; i < heights.length; i++) { //iterate through input array
            Iterator<Helper> myIt = myStack.iterator();
            while (myIt.hasNext()) { //iterate through stack, for testing purposes
                System.out.print(myIt.next().toString());
                System.out.println();
            }
            if (!myStack.isEmpty()) {
                if (heights[i] >= myStack.peek().getValue()) {//if curr element is greater than last, push current element
                    myStack.push(new Helper(heights[i]));
                    System.out.print("added1: "); //testing print statements
                    System.out.println(heights[i]);
                } else {
                    while (heights[i] < myStack.peek().getValue()) { //if current element is less than head of stack, pop elements from stack until current is >= head of stack

                        Helper popped = myStack.pop();
                        poppedLength++;
                        
                        area = (poppedLength + popped.getGapLength()) * popped.getValue();
                        System.out.print(poppedLength + popped.getGapLength()); //print statements for testing
                        System.out.print("  ");
                        System.out.print(popped.getValue());
                        System.out.print("  ");
                        System.out.print(area);
                        System.out.println();
                        if (area > maxArea) maxArea = area; //update max

                        if (myStack.isEmpty()) break;

                        
                    }
                    if (!myStack.isEmpty()) {
                        myStack.peek().setGapLength(poppedLength + myStack.peek().getGapLength());

                    } 
                    
                    myStack.add(new Helper(heights[i], poppedLength)); //push current, THIS IS WHERE THE ERROR IS OCCURING
                    System.out.print("added2: ");
                    System.out.println(heights[i]);
                    
                    poppedLength = 0;
                }
            } else {//if stack is empty for some reason, this actually should never execute
                myStack.push(new Helper(heights[i]));
            }
        }
        
        while (!myStack.isEmpty()) {//remove rest of elements in the stack
            Helper popped = myStack.pop();
            poppedLength++;
            
            area = (poppedLength + popped.getGapLength()) * popped.getValue();
            if (area > maxArea) maxArea = area;
            
            System.out.print(poppedLength + popped.getGapLength());
            System.out.print("  ");
            System.out.print(popped.getValue());
            System.out.print("  ");
            System.out.print(area);
            System.out.println();
            
        }
        
        return maxArea;
    }
    
    class Helper {//the elements of the stack
    
        private int value;
        private int gapLength;

        public Helper(int val) {
            value = val;
            gapLength = 0;
        }
        
        public Helper(int val, int gap) {
            value = val;
            gapLength = gap;
        }

        public int getValue() {
            return value;
        }
        
        public int getGapLength() {
            return gapLength;
        }
        
        public void setGapLength(int length) {
            gapLength = length; 
        }
        
        public String toString() {
            String retStr = "Val: " + Integer.toString(value) + "    Gap:" + Integer.toString(gapLength) + "     ";
            return retStr;
        }
    }
}

Answer 1

您解决问题的方式很好，将其分解为多个函数。但是，调试起来对我们来说很困难。

这会通过：

class Solution {
    public static int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

        int[] leftReduce = new int[height.length];
        int[] rightReduce = new int[height.length];
        rightReduce[height.length - 1] = height.length;
        leftReduce[0] = -1;

        for (int i = 1; i < height.length; i++) {
            int p = i - 1;

            while (p >= 0 && height[p] >= height[i]) {
                p = leftReduce[p];
            }

            leftReduce[i] = p;
        }

        for (int i = height.length - 2; i >= 0; i--) {
            int p = i + 1;

            while (p < height.length && height[p] >= height[i]) {
                p = rightReduce[p];
            }

            rightReduce[i] = p;
        }

        int maxArea = 0;

        for (int i = 0; i < height.length; i++) {
            maxArea = Math.max(maxArea, height[i] * (rightReduce[i] - leftReduce[i] - 1));
        }

        return maxArea;
    }
}

就像问题下的评论一样，我对这行也有点困惑：

Deque<Helper> myStack = new ArrayDeque<Helper>();

参考资料

有关其他详细信息，您可以在其中查看 Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2}。

因为你正在准备 interviews:

我们想写bug-free and clean codes based on standards and conventions (e.g., c^{1, 2}, c++^{1, 2}, java^{1, 2}, c#^{1, 2}, python¹, javascript¹, go¹, rust¹).
面试期间实施解决方案的时间非常有限。确保不会运行因代码设计复杂化而超时。

祝你面试顺利！ ^_^

Answer 2

我无法确切地弄清楚我的错误是什么，但能够通过调用 push() 方法而不是同时调用 push() 和 add() 方法来解决问题。我怀疑这些方法依赖于不能互换使用。

Java ArrayDeque push() 似乎添加到堆栈的 front/tail [潜在错误]

Java ArrayDeque push() seems to add to front/tail of stack [potential bug]

java

debugging

stack

arraydeque

参考资料

因为你正在准备 interviews:

祝你面试顺利！ ^_^