备考华为机试

1.去除重复字母（力扣316）

本题要求按照最小字典序返回，因此采用单调栈。

public String removeDuplicateLetters(String s) {
    Deque<Character> deque = new ArrayDeque<>();
    for (int i = 0; i < s.length(); i++) {
        if(deque.contains(s.charAt(i))){
            continue;
        }
        else {
            while (!deque.isEmpty() && deque.peek()>s.charAt(i) && s.indexOf(deque.peek(),i)!=-1)
                deque.pop();
            deque.push(s.charAt(i));
        }
    }
    StringBuilder sb = new StringBuilder();
    while (!deque.isEmpty()){
        sb.append(deque.pop());
    }
    return sb.reverse().toString();
}

2.下一个更大元素1（力扣496）

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
//        int[] res = new int[nums1.length];
//        for (int i = 0; i < nums1.length; i++) {
//            int j = 0;
//            while (nums1[i] != nums2[j]) j++;
//            for (; j < nums2.length; j++) {
//                if(nums2[j] > nums1[i])
//                {
//                    res[i] = nums2[j];
//                    break;
//                }
//            }
//            if(j == nums2.length)
//                res[i] = -1;
//        }
//        return res;
        Deque<Integer> deque = new ArrayDeque<>();
        int[] res = new int[nums1.length];
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            while (!deque.isEmpty() && nums2[i] > deque.peek()){
                hashMap.put(deque.peek(),nums2[i]);
                deque.pop();
            }
            deque.push(nums2[i]);
        }
        while (!deque.isEmpty())
            hashMap.put(deque.pop(),-1);
        for (int i = 0; i < nums1.length; i++) {
            res[i] = hashMap.get(nums1[i]);
        }
        return res;
    }

3.下一个更大元素2（力扣503）

public int[] nextGreaterElements(int[] nums) {
    Deque<Integer> deque = new ArrayDeque<>();
    int[] res = new int[nums.length];
    Arrays.fill(res,-1);
    for (int i = 0; i < nums.length*2; i++) {
        while (!deque.isEmpty() && nums[i%nums.length]>nums[deque.peek()]){
            res[deque.peek()] = nums[i%nums.length];
            deque.pop();
        }
        deque.push(i% nums.length);
    }
    return res;
}

4.接雨水（42）

可以用双指针找到当前位置左边最高和右边最高，取两者最小值减去当前高度作为高度，宽度为1，类加求和得到答案，时间复杂度为O(n^2)。可以用单调栈，遍历找到在栈顶元素右边比栈顶元素高的元素，用栈顶元素的下一个作为左边最高的，然后继续用取左边最高和右边最高的最小值减去栈顶元素高度作为高度，宽度为右边最高元素（当前元素）下标减去左边最高元素下标再减1。

    public int trap(int[] height) {
//        //双指针，找到当前位置左边最高的和右边最高的，取两者最小值减去当前高度为高度差，宽度为1，累加求和
//        int res = 0;
//        for (int i = 0; i < height.length; i++) {
//            int rMaxHeight = height[i];
//            int lMaxHeight = height[i];
//            for (int r = i+1; r < height.length; r++) {
//                if(height[r] > rMaxHeight)
//                    rMaxHeight = height[r];
//            }
//            for (int l = i-1; l >=0 ; l--) {
//                if(height[l] > lMaxHeight)
//                    lMaxHeight = height[l];
//            }
//            int h = Math.min(lMaxHeight,rMaxHeight) - height[i];
//            //高为h，宽为1
//            res+= h*1;
//        }
//        return res;
        int res = 0;
        //栈中存放下标
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < height.length; i++) {
            if (deque.isEmpty())
                deque.push(i);
            else
                //若小于则直接放
                if(height[i] < height[deque.peek()]){
                    deque.push(i);
                }
                //若相等，更新下标，按右边的算
                else if(height[i] == height[deque.peek()]){
                    deque.pop();
                    deque.push(i);
                }
                //若大于，则计算雨水量,两边最小的高度减去中间高度，乘中间宽度
                else {
                    //要用while把所有满足的都算了
                    while (!deque.isEmpty() && height[i] > height[deque.peek()]){
                        int mid = deque.peek();
                        deque.pop();
                        if(!deque.isEmpty()){
                            int left = deque.peek();
                            int width = i - left-1;
                            //left为左边高度下标，i为右边高度下标
                            int hight = Math.min(height[left],height[i])-height[mid];
                            res += width*hight;
                        }
                    }
                    deque.push(i);
                }
        }
        return res;
    }

*5.柱状图中最大的矩形（力扣84）

单调栈的应用。

    public int largestRectangleArea(int[] heights) {
//        //双指针,向左右分别找比当前高度小的，一旦遇到就break，只保留中间的宽度，乘以当前的高度
//        int max = 0;
//        for (int i = 0; i < heights.length; i++) {
//            int l = i;
//            int r = i;
//            for (; l >=0 ; l--) {
//                if(heights[l] < heights[i])
//                    break;
//            }
//            for (; r < heights.length ; r++) {
//                if(heights[r] < heights[i])
//                    break;
//            }
//            int w = r-l-1;
//            int h = heights[i];
//            max = Math.max(max,w*h);
//        }
//        return max;
        Deque<Integer> deque = new ArrayDeque<>();
        int max = 0;
        // 数组扩容，在头和尾各加入一个元素
        int [] newHeights = new int[heights.length + 2];
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;
        for (int index = 0; index < heights.length; index++){
            newHeights[index + 1] = heights[index];
        }
        heights = newHeights;
        for (int i = 0; i < heights.length; i++) {
            if(deque.isEmpty())
                deque.push(i);
            else
                //若大于直接放
                if(heights[i] > heights[deque.peek()])
                    deque.push(i);
                //若等于则更新下标
                else
                    if(heights[i] == heights[deque.peek()])
                    {
                        deque.pop();
                        deque.push(i);
                    }
                    //若小于则取出计算
                    else {
                        while (heights[i] < heights[deque.peek()]){
                            int mid = deque.pop();
                            int left = deque.peek();
                            int w = i - left - 1;
                            int h = heights[mid];
                            max = Math.max(max,w*h);
                        }
                        deque.push(i);
                    }
        }
        return max;
    }