我相信大多数人都听说过直方图中最大矩形问题。 -链接-
在我的当前项目中,我需要更改该算法以便在直方图中找到所有不属于另一个矩形较小子集的矩形。
目前我已经做到了这一步,但我无法想出如何不计算此处的子集。
在我的当前项目中,我需要更改该算法以便在直方图中找到所有不属于另一个矩形较小子集的矩形。
目前我已经做到了这一步,但我无法想出如何不计算此处的子集。
//time: O(n), space:O(n)
public ArrayList<int[]> largestRectangles(int[] height) {
ArrayList<int[]> listRect = new ArrayList<int[]>();
if (height == null || height.length == 0) {
return null;
}
Stack<Integer> stack = new Stack<Integer>();
int max = 0;
int i = 0;
while (i < height.length) {
//push index to stack when the current height is larger than the previous one
if (stack.isEmpty() || height[i] >= height[stack.peek()]) {
stack.push(i);
i++;
} else {
//add rectangle when the current height is less than the previous one
int p = stack.pop();
int h = height[p];
int w = stack.isEmpty() ? i : i - stack.peek() - 1;
listRect.add(new int[]{p,h,w});
}
}
while (!stack.isEmpty()) {
int p = stack.pop();
int h = height[p];
int w = stack.isEmpty() ? i : i - stack.peek() - 1;
listRect.add(new int[]{p,h,w});
}
return listRect;
}
public static void main(String[] args) {
for(int[] rect : largestRectangles(new int[]{1,2,2,3,3,2})) {
System.out.print("pos:"+rect[0]+" height"+rect[1]+"
width"+rect[2]);
System.out.println();
}
}