1.股票平滑下跌阶段的数目

题目

解析

• 注意点：答案要加上数组长度，单个数字也满足要求；

代码

class Solution {
public:long long getDescentPeriods(vector<int>& prices) {// 时间复杂度：O(n)// 空间复杂度：O(1)int n = prices.size();long long ans = 0;int i = 0;while(i < n){int start = i ++;while(i < n && prices[i] + 1 == prices[i - 1]){i ++;}ans += (long long)(i - start) * (i - start - 1) / 2;}return ans + n;}
};

2.汇总区间

题目

解析

• 题目要求：就是将数组分割为多个连续的区间；
• 注意点：从 i 就要开始判断，更新完答案要 i ++；

代码

class Solution {
public:vector<string> summaryRanges(vector<int>& nums) {// 时间复杂度：O(n)// 空间复杂度：O(1)int n = nums.size();vector<string> ans;int i = 0;while(i < n){string s = to_string(nums[i]);// 从 i 就要开始判断int start = i;while(i < n && nums[i] + 1 == nums[i + 1]){i ++;               }if(start != i) s += "->" + to_string(nums[i]);ans.push_back(s);i ++;// 移动指针}return ans;}
};

3.使数组元素相等的减少操作

题目

解析

• 题目要求：把所有大于最小值的数变为最小值，且变为最小值需要的次数与距离有关；
• 首先要排除所有最小的值，从大于他的数开始遍历；
• 例如：[2,3,4,5,5]，答案计算为 (3 * 1) + (4 * 2) + (5 * 3) * 2；

代码

class Solution {
public:int reductionOperations(vector<int>& nums) {// 时间复杂度：O(nlogn)// 空间复杂度：O(1)int n = nums.size();int ans = 0;sort(nums.begin(),nums.end());int i = 1;while(i < n && nums[i] == nums[i - 1]){i ++;}int k = 1;while(i < n){int start = i ++;while(i < n && nums[i] == nums[i - 1]){i ++;}ans += (i - start) * k;k ++;}return ans;}
};

4.数组中的最长山脉

题目

解析

• 先找到最长递增，再继续沿着找递减子序列；
• 注意点：i 指针要回退，arr[i - 1] 为左峰；

代码

class Solution {
public:int longestMountain(vector<int>& arr) {// 时间复杂度：O(n)// 空间复杂度：O(1)int n = arr.size();int ans = 0;int i = 0;while(i < n){// 找到最长递增子序列int start = i ++;while(i < n && arr[i] > arr[i - 1]){i ++;}if(i - start < 2) continue;// 找到最长递减子序列int start_1 = i - 1;while(i < n && arr[i] < arr[i - 1]){i ++;}if(i - start_1 < 2) continue;ans = max(ans,i - start);i --;// 必须回退一位，arr[i - 1] < arr[i]，是左峰}return ans;}
};