896. 单调数列 && 740. 删除与获得点数

896. 单调数列

题目

如果数组是单调递增或单调递减的，那么它是单调的。

如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。 如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。

当给定的数组 A 是单调数组时返回 true，否则返回 false。

示例 1：

输入：[1,2,2,3]
输出：true
示例 2：

输入：[6,5,4,4]
输出：true
示例 3：

输入：[1,3,2]
输出：false
示例 4：

输入：[1,2,4,5]
输出：true
示例 5：

输入：[1,1,1]
输出：true

思路

设立一个base判断当前是单调递增还是单调递减

code

class Solution {
    public boolean isMonotonic(int[] A) {
        int n=A.length;
        int base=0;
        for(int i=0;i<n-1;i++){
            if(A[i]<A[i+1] && base==0){
                base=1;
            }else if(A[i]>A[i+1] && base==0){
                base=-1;
            }else if(base==1){
                if(A[i]>A[i+1]) return false;
            }else if(base==-1){
                if(A[i]<A[i+1]) return false;
            }
        }
        return true;
    }
}

740. 删除与获得点数

题目

给定一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1:

输入: nums = [3, 4, 2]
输出: 6
解释:
删除 4 来获得 4 个点数，因此 3 也被删除。
之后，删除 2 来获得 2 个点数。总共获得 6 个点数。
示例 2:

输入: nums = [2, 2, 3, 3, 3, 4]
输出: 9
解释:
删除 3 来获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

思路

联想到打家劫舍，也是相邻的位置不能抢，但是打家劫舍是物理位置上的相邻，这个题目是逻辑位置上的邻近。所以要把逻辑位置转换成物理位置，此时可以运用桶的思想，把数组中的数字当作下标放入桶中。

code

class Solution {
    public int deleteAndEarn(int[] nums) {
        int n=nums.length;
        if(n==0) return 0;
        if(n==1) return nums[0];
        int max=Integer.MIN_VALUE;
        for(int num:nums){
            max=Math.max(max,num);
        }
        int[] count=new int[max+1];
        for(int num:nums){
            count[num]++;
        }
        int[] dp=new int[max+1];
        dp[1]=count[1];
        for(int i=2;i<=max;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+i*count[i]);
        }
        return dp[max];
    }
}