Я работаю над вопросом 84 leetcode, максимальные прямоугольники. При тестировании я сталкивался с этим странным случаем, когда кажется, что стек складывается в хвост. Я подтвердил это, используя операторы печати и объект-итератор.
Тестовый пример: [4,2,0,3,2,5]
предпоследний элемент в массиве, 2, кажется, выталкивается в хвост, прямо под 0 (Его следует подтолкнуть вверх. В моих операторах печати val: x gap: y появляется, когда элемент выталкивается, xyz появляется, когда элемент выталкивается и добавляется : 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;
}
}
}