896. 單調(diào)數(shù)列

題目

如果數(shù)組是單調(diào)遞增或單調(diào)遞減的，那么它是單調(diào)的。

如果對于所有 i <= j，A[i] <= A[j]，那么數(shù)組 A 是單調(diào)遞增的。 如果對于所有 i <= j，A[i]> = A[j]，那么數(shù)組 A 是單調(diào)遞減的。

當給定的數(shù)組 A 是單調(diào)數(shù)組時返回 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判斷當前是單調(diào)遞增還是單調(diào)遞減

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. 刪除與獲得點數(shù)

題目

給定一個整數(shù)數(shù)組 nums ，你可以對它進行一些操作。

每次操作中，選擇任意一個 nums[i] ，刪除它并獲得 nums[i] 的點數(shù)。之后，你必須刪除每個等于 nums[i] - 1 或 nums[i] + 1 的元素。

開始你擁有 0 個點數(shù)。返回你能通過這些操作獲得的最大點數(shù)。

示例 1:

輸入: nums = [3, 4, 2]
輸出: 6
解釋:
刪除 4 來獲得 4 個點數(shù)，因此 3 也被刪除。
之后，刪除 2 來獲得 2 個點數(shù)?？偣搏@得 6 個點數(shù)。
示例 2:

輸入: nums = [2, 2, 3, 3, 3, 4]
輸出: 9
解釋:
刪除 3 來獲得 3 個點數(shù)，接著要刪除兩個 2 和 4 。
之后，再次刪除 3 獲得 3 個點數(shù)，再次刪除 3 獲得 3 個點數(shù)。
總共獲得 9 個點數(shù)。

思路

聯(lián)想到打家劫舍，也是相鄰的位置不能搶，但是打家劫舍是物理位置上的相鄰，這個題目是邏輯位置上的鄰近。所以要把邏輯位置轉(zhuǎn)換成物理位置，此時可以運用桶的思想，把數(shù)組中的數(shù)字當作下標放入桶中。

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];
    }
}