【甘泉算法】一文搞定单调栈问题

/**
 * 暴力解法：O(n^2)
 *
 * @param nums 数组
 * @return 输出数组
 */
public int[] nextGreaterElement(int[] nums) {
    int[] result = new int[nums.length];
    // 遍历到倒数第二个元素即可，最后一个元素直接赋值为-1
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] > nums[i]) {
                result[i] = nums[j];
                break;
            }
            if (j == nums.length - 1) {
                result[i] = -1;
            }
        }
    }
    result[nums.length - 1] = -1;
    return result;
}

public int[] nextGreaterElement(int[] nums) {
    int[] result = new int[nums.length];
    Stack<Integer> stack = new Stack<>();
    for (int i = nums.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && nums[i] >= stack.peek()) {
            stack.pop();
        }
        result[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(nums[i]);
    }
    return result;
}

public int[] dailyTemperatures(int[] temperatures) {
    int[] result = new int[temperatures.length];
    Stack<Integer> stack = new Stack<>();
    for (int i = temperatures.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {
            stack.pop();
        }
        // 求取距离就是两索引的差
        result[i] = stack.isEmpty() ? 0 : stack.peek() - i;
        // 存储当前元素的索引
        stack.push(i);
    }
    return result;
}

/**
 * 使用map记录nums2中每个元素和下一个更大元素的关系：O(n)
 *
 * @param nums1 数组1
 * @param nums2 数组2
 * @return 数组
 */
public int[] nextGreaterElement2(int[] nums1, int[] nums2) {
    // 设置一个Map来存储nums2中每个元素和它下一个更大元素的关系
    Map<Integer, Integer> map = new HashMap<>((int) (nums2.length / 0.75) + 1);
    Stack<Integer> stack = new Stack<>();
    for (int i = nums2.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && nums2[i] > stack.peek()) {
            stack.pop();
        }
        // 使用map将nums2中的每个元素与其下一个更大元素关联起来
        map.put(nums2[i], stack.isEmpty() ? -1 : stack.peek());
        stack.push(nums2[i]);
    }
    // 遍历nums1，下一个更大元素
    for (int i = 0; i < nums1.length; i++) {
        nums1[i] = map.get(nums1[i]);
    }
    return nums1;
}

/**
 * 环状数组常用的做法就是就是使用模的形式来模拟数组有环，实际是没有增加任何空间
 *
 * @param nums 数组
 * @return 数组
 */
public int[] nextGreaterElements(int[] nums) {
    int[] result = new int[nums.length];
    Stack<Integer> stack = new Stack<>();
    for (int i = nums.length * 2 - 1; i >= 0; i--) {
        while (!stack.isEmpty() && nums[i % nums.length] >= stack.peek()) {
            stack.pop();
        }
        result[i % nums.length] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(nums[i % nums.length]);
    }
    return result;
}

public class StockSpanner {
	
	/**
     * 栈priceStack和widthStack分别用来记录元素和跨跨度
     */
    private final Stack<Integer> priceStack;
    private final Stack<Integer> widthStack;

    public StockSpanner() {
        this.priceStack = new Stack<>();
        this.widthStack = new Stack<>();
    }

    public int next(int price) {
    	// 跨度至少为1，就是自身，所以这里是1，如果不包含自身，那么这里就是0
        int width = 1;
        while (!priceStack.isEmpty() && priceStack.peek() <= price) {
            priceStack.pop();
            width += widthStack.pop();
        }
        priceStack.push(price);
        widthStack.push(width);
        return width;
    }
}

/**
 * 移除字符串中K个数字
 *
 * @param num 数字字符串例如1432219
 * @param k 移除K个数字
 * @return 最小数字
 */
public String removeKdigits(String num, int k) {
    // 处理特殊情况
    if (k == num.length()) {
        return "0";
    }
    // 使用单调栈思想来解题
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < num.length(); i++) {
        while (k > 0 && !stack.isEmpty() && num.charAt(i) < stack.peek()) {
            stack.pop();
            k--;
        }
        // 这里做一个特殊处理，防止首位为0的入栈
        if (num.charAt(i) != '0' || !stack.isEmpty()) {
            stack.push(num.charAt(i));
        }
    }
    // 如果没有完成所有K个数字的移除，那么直接移除低位数，因为出现没有移除完的情况是因为一直再递增
    while (k > 0 && !stack.isEmpty()) {
        stack.pop();
        k--;
    }
    return stack.size() == 0 ? "0" : stack2String(stack);
}

/**
 * 将一个不为空的stack内的元素转换成字符串
 *
 * @param stack 栈
 * @return 字符串
 */
private String stack2String(Stack<Character> stack) {
    StringBuilder result = new StringBuilder();
    while (!stack.isEmpty()) {
        result.insert(0, stack.pop());
    }
    return result.toString();
}

/**
 * 排序+双指针算法：O(nlogn)
 *
 * @param nums 数组
 * @return 最短无序连续子数组长度
 */
public int findUnsortedSubarray(int[] nums) {
    int[] nums2 = nums.clone();
    Arrays.sort(nums2);
    int start = nums2.length;
    int end = 0;
    for (int i = 0; i < nums2.length; i++) {
        if (nums[i] != nums2[i]) {
            start = Math.min(start, i);
            end = Math.max(end, i);
        }
    }
    return end - start >= 0 ? end - start + 1 : 0;
    }

/**
 * 单调栈解法：O(n)
 *
 * @param nums 数组
 * @return 最短无序连续子数组长度
 */
public int findUnsortedSubarray(int[] nums) {
    int left = nums.length - 1;
    int right = 0;
    // 单调递增栈
    Stack<Integer> incrementalStack = new Stack<>();
    for (int i = 0; i < nums.length; i++) {
        while (!incrementalStack.isEmpty() && nums[incrementalStack.peek()] > nums[i]) {
            left = Math.min(left, incrementalStack.pop());
        }
        incrementalStack.push(i);
    }
    // 单调递减栈
    Stack<Integer> decreasingStack = new Stack<>();
    for (int i = nums.length - 1; i >= 0; i--) {
        while (!decreasingStack.isEmpty() && nums[decreasingStack.peek()] < nums[i]) {
            right = Math.max(right, decreasingStack.pop());
        }
        decreasingStack.push(i);
    }
    return right > left ? right - left + 1 : 0;
}

/**
 * 暴力解法：O(n^2)，超出时间限制，固定高度，找到左右边界，它的边界是左右遇见的第一个比它矮的柱子
 *
 * @param heights 高度数组
 * @return 面积
 */
public int largestRectangleArea(int[] heights) {
    int area = 0;
    for (int i = 0; i < heights.length; i++) {
        int left = i;
        int right = i;
        int height = heights[i];
        while (left > 0 && heights[left - 1] >= height) {
            left--;
        }
        while (right < heights.length - 1 && heights[right + 1] >= height) {
            right++;
        }
        area = Math.max(height * (right - left + 1), area);
    }
    return area;
}

/**
 * 单调栈+哨兵解法：O(n)
 *
 * @param heights 高度数组
 * @return 最大面积
 */
public int largestRectangleArea(int[] heights) {
    if (heights.length == 0) {
        return 0;
    }
    if (heights.length == 1) {
        return heights[0];
    }
    // 面积
    int area = 0;
    // 添加哨兵:数组两端各加上一个为0的元素
    int[] newHeights = new int[heights.length + 2];
    System.arraycopy(heights, 0, newHeights, 1, heights.length);
    newHeights[0] = 0;
    newHeights[heights.length + 1] = 0;
    heights = newHeights;

    // 单调栈
    Stack<Integer> stack = new Stack<>();
    // 加入哨兵，stack中就无需做非空判断，因为0索引对应的高度为0，肯定是数组中最小的
    stack.push(0);
    for (int i = 1; i < heights.length; i++) {
        while (heights[i] < heights[stack.peek()]) {
            int currentHeight = heights[stack.pop()];
            int currentWight = i - stack.peek() - 1;
            area = Math.max(area, currentHeight * currentWight);
        }
        stack.push(i);
    }
    return area;
}

/**
 * 单调栈：O(n)
 *
 * @param height 高度数组
 * @return 雨水面积
 */
public int trap(int[] height) {
    // 对于数组个数为0，1，2均无法接到雨水，所以为0
    if (height.length == 0 || height.length == 1 || height.length == 2) {
        return 0;
    }
    // 构建单调递减栈
    Stack<Integer> stack = new Stack<>();
    // 记录雨水面积
    int rainWaterArea = 0;
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
            int currentIndex = stack.pop();
            if (stack.isEmpty()) {
                break;
            }
            // 获取左边界需要使用peek，而不能使用pop，这是因为需要一层一层计算雨水面积
            int leftIndex = stack.peek();
            int currentHeight = Math.min(height[leftIndex], height[i]) - height[currentIndex];
            rainWaterArea += currentHeight * (i - leftIndex - 1);
        }
        stack.push(i);
    }
    return rainWaterArea;
}

public String removeDuplicateLetters(String s) {
    // 字符串是小写字母组成，小写字母a~z的ascii的取值范围是97~122
    // 创建一个数组记录栈中是否已经有了该字符，默认值均为false
    boolean[] inStackArray = new boolean[26];
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        // 如果字符已经在栈中了，那么就不再进栈了
        if (inStackArray[c % 97]) {
            continue;
        }
        stack.push(c);
        inStackArray[c % 97] = true;
    }
    // 将栈中的元素取出拼成字符串
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        sb.append(stack.pop());
    }
    return sb.reverse().toString();
}

public String removeDuplicateLetters(String s) {
    // 字符串是小写字母组成，小写字母a~z的ascii的取值范围是97~122
    // 创建一个数组记录栈中是否已经有了该字符，默认值均为false
    boolean[] inStackArray = new boolean[26];
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        // 如果字符已经在栈中了，那么就不再进栈了
        if (inStackArray[c % 97]) {
            continue;
        }
        // 构建单调递增栈
        while (!stack.isEmpty() && stack.peek() > c) {
            inStackArray[stack.pop() % 97] = false;
        }
        stack.push(c);
        inStackArray[c % 97] = true;
    }
    // 将栈中的元素取出拼成字符串
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        sb.append(stack.pop());
    }
    return sb.reverse().toString();
}

/**
 * 单调栈：O(n)
 *
 * @param s 字符串
 * @return 去除重复字母后的字符串
 */
public String removeDuplicateLetters(String s) {
    // 字符串是小写字母组成，小写字母a~z的ascii的取值范围是97~122
    // 创建一个26个英文字母的数组来记录每个小写字母出现的次数
    int[] count = new int[26];
    for (char c : s.toCharArray()) {
        count[c % 97]++;
    }
    // 创建一个数组记录栈中是否已经有了该字符，默认值均为false
    boolean[] inStackArray = new boolean[26];
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        // 每遍历一个字符，该字符出现的次数就少一次
        count[c % 97]--;
        // 如果字符已经在栈中了，那么就不再进栈了
        if (inStackArray[c % 97]) {
            continue;
        }
        // 构建单调递增栈
        while (!stack.isEmpty() && stack.peek() > c) {
            if (count[stack.peek() % 97] == 0) {
                break;
            }
            inStackArray[stack.pop() % 97] = false;
        }
        stack.push(c);
        inStackArray[c % 97] = true;
    }
    // 将栈中的元素取出拼成字符串
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        sb.append(stack.pop());
    }
    return sb.reverse().toString();
}