问题描述：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
解析：另设置一个min栈，数据栈进元素的时候min栈也添加元素，若当前元素比栈顶小则其入栈，否则栈顶元素在此入栈（保持栈顶元素为当前情况最小）。
Stack<Integer> stack = new Stack<Integer>();
Stack<Integer> minstack = new Stack<Integer>();
int size = 0;
public void push(int node) {
stack.push(node);
if (minstack.isEmpty() || node < minstack.peek()){
minstack.push(node);
}else{
minstack.push(minstack.peek());
}
size++;
}
public void pop() {
if (size > 0){
stack.pop();
minstack.pop();
size--;
}
}
public int top() {
if (size > 0){
return stack.peek();
}
return 0;
}
public int min() {
if (size > 0){
return minstack.peek();
}
return 0;
}问题描述：给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
解析：largestRectangleArea()为标准的单调栈函数，栈底到栈顶按照从小到大的顺序，若是要入栈的元素小于栈顶元素，让其直接入栈就会破坏单调结构，因此逐个出栈直至待入栈元素能够入栈。而一个元素出栈的时候，让其出栈的元素就是其右边界，出栈后栈顶元素为其左边界。
public int maximalRectangle(char[][] map) {
if (map == null || map.length == 0 || map[0].length == 0){ return 0;}
int maxArea = 0;
int[] height = new int[map[0].length];
for (int i = 0; i < map.length; i++){
for (int j = 0; j < map[0].length; j++){
height[j] = map[i][j] == '0' ? 0 : height[j] + 1;
}
maxArea = Math.max(largestRectangleArea(height), maxArea);
}
return maxArea;
}
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<Integer>();
int res = 0;
for (int i = 0; i < heights.length; i++){
//要入栈的元素比栈顶元素小就需要将栈顶元素出栈
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
//元素出栈就需要计算面积，让其出栈的元素比他小为右边界，其在栈中下一个元素比他小为其左边界
int cur = stack.pop();
int leftBorder = stack.isEmpty() ? -1 : stack.peek();
res = Math.max(res, heights[cur] * (i - leftBorder - 1));
}
stack.push(i);
}
while (!stack.isEmpty()){
//栈中还未出栈的元素右边界都是数组边界（因为没有一个比其小的元素能让其出栈）
int cur = stack.pop();
int leftBorder = stack.isEmpty() ? -1 : stack.peek();
res = Math.max(res, heights[cur] * (heights.length - leftBorder - 1));
}
return res;
}问题描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
解析：该题目为单调栈的变体，栈底到栈顶按照从大到小的顺序，若是要入栈的元素小于栈顶元素，让其直接入栈就会破坏单调结构，因此逐个出栈直至待入栈元素能够入栈。而一个元素出栈的时候，让其出栈的元素就是其右边界，出栈后栈顶元素为其左边界，计算面积高为左右边界较小者，长度为左右边界的距离。
public int trap(int[] height) {
if (height == null || height.length <= 2)return 0;
Stack<Integer> stack = new Stack<Integer>();
int res = 0;
int curIndex = 0;
while (curIndex < height.length){
while (!stack.isEmpty() && height[stack.peek()] < height[curIndex]){
int cur = stack.pop();
if (stack.isEmpty()){
break;
}
int left = stack.peek();
int distance = curIndex - left - 1;
res += distance * (Math.min(height[curIndex], height[left])- height[cur]);
}
stack.push(curIndex++);
}
return res;
}问题描述：如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
解析：维护两个大根堆与小根堆（优先级队列），小根堆存最大的一半数，大根堆存最小的一半数。奇数个数的时候，将其存入大根堆，然后大根堆堆顶存到小根堆中（如此最大的前一半数都在小根堆中），反之反之。
private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, Comparator.comparingInt(o -> -o));
int count = 0;
public void Insert(Integer num) {
if (count % 2 == 0){
maxHeap.offer(num);
int max = maxHeap.poll();
minHeap.offer(max);
}else{
minHeap.offer(num);
int min = minHeap.poll();
maxHeap.offer(min);
}
count++;
}
public Double GetMedian() {
if(count==0)
throw new RuntimeException("no available number!");
if (count % 2 == 0){
return new Double((maxHeap.peek() + minHeap.peek()))/2;
}else{
return new Double(minHeap.peek());
}
}问题描述：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值
解析：维护一个双端队列，队列中顺序从大到小，每一个数进入队列都要从队列底开始抛出元素使其仍旧满足从大到小顺序。且要注意检查队列头部元素有没有过期。
public ArrayList<Integer> maxInWindows(int [] num, int size){
if (num == null || num.length < size || size < 1)return new ArrayList<Integer>();
ArrayList<Integer> res = new ArrayList<Integer>();
LinkedList<Integer> qMax = new LinkedList<Integer>();
for (int i = 0; i < num.length; i++){
while(!qMax.isEmpty() && num[qMax.peekLast()] <= num[i]){
qMax.pollLast();
}
qMax.addLast(i);
if (qMax.peekFirst() < i - size + 1){
qMax.pollFirst();
}
if (i + 1 - size >= 0){
res.add(num[qMax.peekFirst()]);
}
}
return res;
}