Java每日一练(20230407) 数据流变为多个不相交区间、最小栈、柱状图中最大的矩形

class SummaryRanges {
    private final TreeSet<Integer> tree = new TreeSet<>();
    public void addNum(int val) {
        tree.add(val);
    }
    public int[][] getIntervals() {
        ArrayList<int[]> result = new ArrayList<>(1 << 2);
        Iterator<Integer> iterator = tree.iterator();
        int[] array = new int[tree.size()];
        int i = 0;
        while (iterator.hasNext())
            array[i++] = iterator.next();
        int length = array.length;
        if (length == 0)
            return result.toArray(new int[0][]);
        int start = array[0];
        for (i = 0; i < length; ++i) {
            if (i + 1 < length && array[i + 1] - array[i] != 1) {
                result.add(new int[] { start, array[i] });
                start = array[i + 1];
            } else if (i + 1 == length) {
                result.add(new int[] { start, array[i] });
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

class MinStack {
    Stack<Integer> data_stack;
    Stack<Integer> min_stack;
    /** initialize your data structure here. */
    public MinStack() {
        data_stack = new Stack<Integer>();
        min_stack = new Stack<Integer>();
    }
    public void push(int x) {
        data_stack.push(x);
        if (min_stack.isEmpty()) {
            min_stack.push(x);
        } else {
            if (x > min_stack.peek()) {
                x = min_stack.peek();
            }
            min_stack.push(x);
        }
    }
    public void pop() {
        data_stack.pop();
        min_stack.pop();
    }
    public int top() {
        return data_stack.peek();
    }
    public int getMin() {
        return min_stack.peek();
    }
}
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

import java.util.*;
public class largestRectangleArea {
    public static class Solution {
        public int largestRectangleArea(int[] heights) {
            int length = heights.length;
            if (length == 0) {
                return 0;
            }
            int maxSize = 0;
            for (int i = 0; i < length; i++) {
                int nowHeight = heights[i];
                int nowWidth = 0;
                for (int j = i; j < length; j++) {
                    if (heights[j] < nowHeight) {
                        nowHeight = heights[j];
                    }
                    nowWidth++;
                    if (maxSize < nowHeight * nowWidth) {
                        maxSize = nowHeight * nowWidth;
                    }
                }
            }
            return maxSize;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] heights = {2,1,5,6,2,3};
        System.out.println(s.largestRectangleArea(heights));
    }
}

import java.util.*;
public class largestRectangleArea {
    public static class Solution {
        public int largestRectangleArea(int[] heights) {
            int n = heights.length;
            int[] left = new int[n];  // 存储每个矩形左边第一个小于它的矩形的下标
            int[] right = new int[n];  // 存储每个矩形右边第一个小于它的矩形的下标
            Stack<Integer> stack = new Stack<>();  // 单调栈，存储矩形的下标
            for (int i = 0; i < n; i++) {
                while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                    stack.pop();
                }
                left[i] = stack.isEmpty() ? -1 : stack.peek();
                stack.push(i);
            }
            stack.clear();
            for (int i = n - 1; i >= 0; i--) {
                while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                    stack.pop();
                }
                right[i] = stack.isEmpty() ? n : stack.peek();
                stack.push(i);
            }
            int maxArea = 0;
            for (int i = 0; i < n; i++) {
                int area = (right[i] - left[i] - 1) * heights[i];  // 计算以当前矩形为高的最大面积
                maxArea = Math.max(maxArea, area);
            }
            return maxArea;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] heights = {2,1,5,6,2,3};
        System.out.println(s.largestRectangleArea(heights));
    }
}