[TOC]
给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
说明 :
输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 ，所以升序的意思是<=。
class Solution {
public int findUnsortedSubarray(int[] nums) {
Deque<Integer> stack = new LinkedList<>();
int left = nums.length, right = 0;
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[stack.peekFirst()] > nums[i]) {
left = Math.min(left, stack.pollFirst());
}
stack.offerFirst(i);
}
stack.clear();
for (int i = nums.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[stack.peekFirst()] < nums[i]) {
right = Math.max(right, stack.pollFirst());
}
stack.offerFirst(i);
}
return right - left > 0 ? right - left + 1 : 0;
}
}给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
示例:
输入: [2,1,5,6,2,3] 输出: 10
class Solution {
public int largestRectangleArea(int[] heights) {
int len = heights.length;
if (len == 0) {
return 0;
}
if (len == 1) {
return heights[0];
}
int[] newHeights = new int[len + 2];
for (int i = 0; i < len; ++i) {
newHeights[i + 1] = heights[i];
}
int maxArea = 0;
len += 2;
heights = newHeights;
Deque<Integer> stack = new LinkedList<>();
stack.addFirst(0);
// 栈中存储数组中递增的元素下标，如果栈顶元素大于下一元素就出栈
for (int i = 1; i < len; ++i) {
while (heights[stack.peekFirst()] > heights[i]) {
int height = heights[stack.removeFirst()];
int width = i - stack.peekFirst() - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.addFirst(i);
}
return maxArea;
}
}给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6
详解见leetcode，可以对比leetcode 84
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) {
return 0;
}
int ans = 0;
int rowLen = matrix.length;
int columnLen = matrix[0].length;
// dp数组存储的是长方形的高度
int[] dp = new int[columnLen];
for (int i = 0; i < rowLen; i++) {
for (int j = 0; j < columnLen; j++) {
dp[j] = matrix[i][j] == '1' ? dp[j] + 1 : 0;
}
ans = Math.max(ans, maxArea(dp));
}
return ans;
}
private int maxArea(int[] heights) {
Deque<Integer> stack = new LinkedList<>();
stack.offerFirst(-1);
int maxarea = 0;
for (int i = 0; i < heights.length; i++) {
while (stack.peekFirst() != -1 && heights[stack.peekFirst()] >= heights[i]) {
maxarea = Math.max(maxarea, heights[stack.pollFirst()] * (i - stack.peekFirst() - 1));
}
stack.offerFirst(i);
}
while (stack.peekFirst() != -1) {
maxarea = Math.max(maxarea, heights[stack.pollFirst()] * (heights.length - stack.peekFirst() - 1));
}
return maxarea;
}
}输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true
提示：
数组长度 <= 1000
详解见leetcode
后序遍历的倒序就是先序遍历的先访问根节点，再访问右子树，再访问左子树。
每次遍历找到root节点，如果当前结点的值小于root节点，说明就是合法的。
class Solution {
public boolean verifyPostorder(int[] postorder) {
Deque<Integer> stack = new LinkedList<>();
int root = Integer.MAX_VALUE;
for (int i = postorder.length - 1; i >= 0; i--) {
if (postorder[i] > root) {
return false;
}
while (!stack.isEmpty() && stack.peekFirst() > postorder[i]) {
root = stack.pollFirst();
}
stack.addFirst(postorder[i]);
}
return true;
}
}