递归、排序、贪心 6/1 31-35

排序 + 贪心
注意：这道题是对气球的右边界进行排序

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) {
            return 0;
        }
        Arrays.sort(points, new Comparator() {
            public int compare(int[] point1, int[] point2) {
                if (point1[1] > point2[1]) {
                    return 1;
                } else if (point1[1] < point2[1]) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });
        int pos = points[0][1];
        int ans = 1;
        for (int[] balloon: points) {
            if (balloon[0] > pos) {
                pos = balloon[1];
                ++ans;
            }
        }
        return ans;
    }
}

贪心算法 + 单调栈
单调栈用来减少时间复杂度

class Solution {
          public String removeKdigits(String num, int k) {
            //双端队列模拟单调栈
            Deque deque = new LinkedList<>();
            for (int i = 0; i < num.length(); i++) {
                char cur = num.charAt(i);
                //栈不为空，并且栈顶元素大于当前元素，并且移除元素还没有到达k个
                while (!deque.isEmpty() && deque.peekLast() > cur && k > 0) {
                    deque.removeLast();
                    k--;
                }
                deque.addLast(cur);
            }
            for (int i = 0; i < k; i++) {
                deque.removeLast();
            }
            //去除前导0
            while (!deque.isEmpty() && deque.peekFirst() == '0') deque.removeFirst();
            StringBuilder ans = new StringBuilder();
            //从头开始取出，双端队列的特性
            while (!deque.isEmpty()) ans.append(deque.removeFirst());
            return ans.length() == 0 ? "0" : ans.toString();
        }
}

贪心选择

class Solution {
       public boolean canJump(int[] nums) {
            int max = 0;
            //每一步都选出最远可以到达的距离
            for (int i = 0; i < nums.length - 1; i++) {
                max = Math.max(max,i + nums[i]);//动态维护可以到达的最远的位置
                //不可以继续走下去了此时最远距离等于i，且当前位置无法跳跃
                if (max == i && nums[i] == 0)return false;
                if (max >= nums.length - 1)return true;
            }
            return max >= nums.length - 1;
        }
}

方法一：动态规划

  class Solution {
        public int wiggleMaxLength(int[] nums) {
            int len = nums.length;
            if (len < 2) return len;
            int[] up = new int[len];//前i个元素中末尾呈上升趋势
            int[] down = new int[len];//前i个元素中末尾呈下降趋势
            up[0] = down[0] = 1;
            for (int i = 1; i < len; i++) {
                if (nums[i] > nums[i - 1]) {
                    up[i] = Math.max(up[i - 1], down[i - 1] + 1);
                    down[i] = down[i - 1];
                } else if (nums[i] < nums[i - 1]) {
                    up[i] = up[i - 1];
                    down[i] = Math.max(down[i - 1], up[i - 1] + 1);
                } else {
                    up[i] = up[i - 1];
                    down[i] = down[i - 1];
                }
            }

            return Math.max(up[len - 1], down[len - 1]);
        }
    }

方法二：动态规划 优化
动态规划的优化往往可以寻找降低空间复杂度的办法

class Solution {
 public int wiggleMaxLength(int[] nums) {
            int len = nums.length;
            if (len < 2) return len;
            int up = 1;
            int down = 1;
            for (int i = 1; i < len; i++) {
                if (nums[i] > nums[i - 1]) {
                    //down = down;不需改变
                    up = Math.max(down + 1,up);
                } else if (nums[i] < nums[i - 1]) {
                   down = Math.max(down,up + 1);
                   //up = up;不需改变
                } 
            }

            return Math.max(up, down);
        }
}

方法三：贪心算法

class Solution {
 public int wiggleMaxLength(int[] nums) {
            if (nums.length < 2)return 1;
            int prediff = nums[1] - nums[0];
            int ans = prediff != 0 ? 2 : 1;
            for (int i = 2; i < nums.length; i++) {
                int diff = nums[i] - nums[i - 1];
                if ((diff < 0 && prediff >= 0) || (diff > 0 && prediff <= 0)){
                    ans++;
                    prediff = diff;
                }
            }
            return ans;
        }
}

贪心算法
不断寻找可以获得最大利润的两天

class Solution {
        public int maxProfit(int[] prices) {
            int n = prices.length;
            if (n < 2)return 0;
            int ans = 0;
            boolean flag = false;//false表示手中还没买股票
            int x = 0;
            for (int i = 0; i < n; i++) {
                if (!flag){//如果还未买入，则买入
                    x = prices[i];
                    flag = true;
                }else if (prices[i] < x){
                    x = prices[i];//如果当前股票值比已经买入还低，则重新买入
                }else if (prices[i] > x && i == n - 1){//已经是最后一天了，看是否可以出售
                    ans += prices[i] - x;
                    flag = false;
                }else if (prices[i] > x && i + 1 < n && prices[i + 1] <= prices[i]){
                    //不是最后一天，且明天卖出不会卖更多钱，所以今天卖出
                    ans += prices[i] - x;
                    flag = false;
                }
            }
            return ans;
        }
}