将字符串翻转到单调递增

问题描述：

如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是单调递增的。
我们给出一个由字符 '0' 和 '1' 组成的字符串 S，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。
返回使 S 单调递增的最小翻转次数。

示例 1：
输入："00110"
输出：1
解释：我们翻转最后一位得到 00111.

示例 2：
输入："010110"
输出：2
解释：我们翻转得到 011111，或者是 000111。

示例 3：
输入："00011000"
输出：2
解释：我们翻转得到 00000000。
 
提示：
1 <= S.length <= 20000
S 中只包含字符 '0' 和 '1'

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flip-string-to-monotone-increasing

思路：

还是太菜了...
最开始的时候试图从第一个非0的位置开始计算，如果后面的0多就将0变1，否则将1变0。
这种想法当然是错误的~
后来发现如果最后连续位置是1的话，根本没没必要算进来，于是做了一些改进，从第一个非0位置开始到最后一个0位置截至，判断0和1的个数，并相应做出转变。
emmmm，这么想也不对！emmmm,不出所料...
然后，评论区的大佬是这样子想的：

题解：

使数组唯一的最小增量

给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。

返回使 A 中的每个值都是唯一的最少操作次数。

示例 1:
输入：[1,2,2]
输出：1
解释：经过一次 move 操作，数组将变为 [1, 2, 3]。

示例 2:
输入：[3,2,1,2,1,7]
输出：6
解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。
可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique

思路：

将数组排序，进行一系列的增量操作后，保证数组每个数都唯一，最后得到的结果一定是单调递增的。
具体操作：1、将数组排序。
2、第一次操作时A[i+1]一定大于等于A[i]。如果A[i+1]==A[i],将A[i+1]++,同时，记录所有增量的count++。
3、有了第一次操作后，A[i+1]可能<、>、或者=A[i]。如果等于，操作同上。如果>不用操作。如果<,A[i+1]=A[i]+1;count=count+A[i]+1-A[i+1]。
大概就是这样子！

题解:

class Solution {
public:
    int minIncrementForUnique(vector<int> &A) {
        int n=A.size();
        sort(A.begin(),A.end());
        int count=0;
        for(int i=0;i<n-1;i++){
            if(A[i]==A[i+1]){
                A[i+1]++;
                count++;
            } else if(A[i]>A[i+1]){
                count=count+A[i]+1-A[i+1];
                A[i+1]=A[i]+1;
            }
        }
        return count;
    }
};

全局倒置与局部倒置

问题描述：

数组 A 是 [0, 1, ..., N - 1] 的一种排列，N 是数组 A 的长度。全局倒置指的是 i,j 满足 0 <= i < j < N 并且 A[i] > A[j] ，局部倒置指的是 i 满足 0 <= i < N 并且 A[i] > A[i+1] 。
当数组 A 中全局倒置的数量等于局部倒置的数量时，返回 true 。

示例 1:
输入: A = [1,0,2]
输出: true
解释: 有 1 个全局倒置，和 1 个局部倒置。

示例 2:
输入: A = [1,2,0]
输出: false
解释: 有 2 个全局倒置，和 1 个局部倒置。

注意:
A 是 [0, 1, ..., A.length - 1] 的一种排列
A 的长度在 [1, 5000]之间
这个问题的时间限制已经减少了。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/global-and-local-inversions

思路：

当一个数字与其对应的角标偏移超过1时就会出现局部倒置与全局倒置不同。

题解：

class Solution {
public:
    bool isIdealPermutation(vector<int> &A) {
        int n = A.size();
        for (int i = 0; i < n; i++) {
            if (A[i] - i > 1 || A[i] - i < -1) {
                return false;
            }
        }
        return true;
    }
};

寻找峰值

问题描述：

峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。

示例 1:
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。

示例 2:
输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 你的函数可以返回索引 1，其峰值元素为 2；
  或者返回索引 5， 其峰值元素为 6。

说明:
你的解法应该是 O(logN) 时间复杂度的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-peak-element

思路：

首先，得到数组大小n=nums.size();
因为数组的左右两边的值都为负无穷。如果数组中只有一个数，那么，唯一的数为峰值，如果，数组中有两个数，较大的数为峰值。
当数组的个数大于等于3时，第一种情况，在除两头的中间有峰值，此时峰值的位置满足nums[i] > nums[i - 1] && nums[i] > nums[i + 1]。
另外一种情况，如果中间没有峰值，那么峰值最出现在第一个位置或者最后一个位置。只需判断nums[0]是否大于nums[1]，或者 nums[n - 1]是否大于nums[n - 2]即可。

题解：

class Solution {
public:
    int findPeakElement(vector<int> &nums) {
        int n = nums.size();
        int flag = 0;
        int location;
        if(n==1){
            location=0;
        }
        else if(n==2){
            if(nums[0]>nums[1]){
                location=0;
            } else{
                location=1;
            }
        }
        else{
            for (int i = 1; i <= n - 2; i++) {
                if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                    flag = 1;
                    location = i;
                    break;
                }
            }
            if (flag == 0) {
                if (nums[0] > nums[1]) {
                    location = 0;
                }
                if (nums[n - 2] < nums[n - 1]) {
                    location = n - 1;
                }
            }
        }

        return location;
    }
};

移动石子直到连续 II

问题描述：

在一个长度无限的数轴上，第 i 颗石子的位置为 stones[i]。如果一颗石子的位置最小/最大，那么该石子被称作端点石子。
每个回合，你可以将一颗端点石子拿起并移动到一个未占用的位置，使得该石子不再是一颗端点石子。
值得注意的是，如果石子像 stones = [1,2,5] 这样，你将无法移动位于位置 5 的端点石子，因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。
当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。
要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves] 。

示例 1：
输入：[7,4,9]
输出：[1,2]
解释：
我们可以移动一次，4 -> 8，游戏结束。
或者，我们可以移动两次 9 -> 5，4 -> 6，游戏结束。

示例 2：
输入：[6,5,4,3,10]
输出：[2,3]
解释：
我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。
或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。
注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。

示例 3：
输入：[100,101,104,102,103]
输出：[0,0]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/moving-stones-until-consecutive-ii

思路：

题解：