單調棧

求解一個集合中，每個元素左邊離自己最近且比自己小的元素是？右邊離自己最近且比自己小的元素是？

沒有重複值：

public int[][] getNearLessNoRepeat(int[] arr){
		int[][] res = new int[arr.length][2];
		
		Stack<Integer> stack = new Stack<>();
		
		for (int i = 0; i < res.length; i++) {
			while(!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
				int j = stack.pop();
				int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
				res[j][0] = leftLessIndex;
				res[j][1] = i;
			}
			stack.push(i);
		}
		
		while(!stack.isEmpty()) {
			int j = stack.pop();
			int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
			res[j][0] = leftLessIndex;
			res[j][1] = -1;
		}
		
		return res;
	}
           

有重複值：

public int[][] getNearLess(int[] arr) {
		int[][] res = new int[arr.length][2];
		Stack<List<Integer>> stack = new Stack<>();
		for (int i = 0; i < arr.length; i++) { // i -> arr[i] 進棧
			while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
				List<Integer> popIs = stack.pop();
				int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
				for (Integer popi : popIs) {
					res[popi][0] = leftLessIndex;
					res[popi][1] = i;
				}
			}
      
			if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
				stack.peek().add(Integer.valueOf(i));
			} else {
				ArrayList<Integer> list = new ArrayList<>();
				list.add(i);
				stack.push(list);
			}
		}
		while (!stack.isEmpty()) {
			List<Integer> popIs = stack.pop();
			int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
			for (Integer popi : popIs) {
				res[popi][0] = leftLessIndex;
				res[popi][1] = -1;
			}
		}
		return res;
	}
           

給定一個隻包含正數的數組arr，arr中任何一個子數組sub，一定都可以算出(sub累加和 )* (sub中的最小值)是什麼，那麼所有子數組中，這個值最大是多少？

暴力解：

public static int max1(int[] arr) {
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < arr.length; i++) {
			for (int j = i; j < arr.length; j++) {
				int minNum = Integer.MAX_VALUE;
				int sum = 0;
				for (int k = i; k <= j; k++) {
					sum += arr[k];
					minNum = Math.min(minNum, arr[k]);
				}
				max = Math.max(max, minNum * sum);
			}
		}
		return max;
	}

           

字首和+單調棧

public static int max2(int[] arr) {
		int size = arr.length;
		int[] sums = new int[size];
		sums[0] = arr[0];
		for (int i = 1; i < size; i++) {
			sums[i] = sums[i - 1] + arr[i];
		}
		int max = Integer.MIN_VALUE;
		Stack<Integer> stack = new Stack<Integer>();
		for (int i = 0; i < size; i++) {
			while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
				int j = stack.pop();
				max = Math.max(max, (stack.isEmpty() ? sums[i - 1] : (sums[i - 1] - sums[stack.peek()])) * arr[j]);
			}
			stack.push(i);
		}
      while (!stack.isEmpty()) {
        int j = stack.pop();
        max = Math.max(max, (stack.isEmpty() ? sums[size - 1] : (sums[size - 1] - sums[stack.peek()])) * arr[j]);
      }
		return max;
	}
           

84. 柱狀圖中最大的矩形

給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

示例 1:

輸入：heights = [2,1,5,6,2,3]
輸出：10
解釋：最大的矩形為圖中紅色區域，面積為 10
           

示例 2：

輸入： heights = [2,4]
輸出： 4
           

public int largestRectangleArea(int[] h) {

    	if(h == null || h.length == 0) {
    		return 0;
    	}
    	
    	int maxArea = 0;
    	
    	Stack<Integer> stack = new Stack<>();
    	
    	for (int i = 0; i < h.length; i++) {
    		while(!stack.isEmpty() &&  h[i] <= h[stack.peek()]) {
    			int j = stack.pop();
    			
    			int k = stack.isEmpty() ? -1 : stack.peek();
    			
    			int curArea = (i-k-1) * h[j];
    			maxArea = Math.max(maxArea, curArea);
    		}
    		stack.push(i);
		}
    	
        while (!stack.isEmpty()) {
            // 長
            int j = stack.pop();
            // 寬
			int k = stack.isEmpty() ? -1 : stack.peek();
			
			int curArea = (h.length -k-1) * h[j];
			maxArea = Math.max(maxArea, curArea);
		}
        return maxArea;
    }
}
           

每個人都有潛在的能量，隻是很容易被習慣所掩蓋，被時間所迷離，被惰性所消磨~