打卡第四十二天
2道中等题
题目：
思路：枚举中间元素 j，然后快速找到它左边比它小的最小值，以及右边比它小的最小值。
代码：
class Solution {
public:int minimumSum(vector<int> &nums) {int n = nums.size();vector<int> suf(n);// suf[i]表示从i到数组末尾的最小值）suf[n - 1] = nums[n - 1];for (int i = n - 2; i > 1; i--) {// j最大为n-2，需要suf[j+1]，j+1最小为2suf[i] = min(suf[i + 1], nums[i]);// 取右边最小值(suf[i+1])和当前值(nums[i])中的较小者}int ans = INT_MAX;int pre = nums[0];// pre表示当前j左边部分的最小值，初始化为第一个元素for (int j = 1; j < n - 1; j++) { // j从1开始到n-2结束，因为中间元素至少左右各有一个元素if (pre < nums[j] && nums[j] > suf[j + 1]) { // 左边存在比nums[j]小的数（且pre是这些数中最小的）右边存在比nums[j]小的数（且suf[j+1]是右边最小的）ans = min(ans, pre + nums[j] + suf[j + 1]);// pre + nums[j] + suf[j+1]构成当前找到的三元组的最小和}pre = min(pre, nums[j]);// 更新左边最小值pre，将当前元素纳入左边范围的考量}return ans == INT_MAX ? -1 : ans;// 如果ans没有被更新过（仍然是INT_MAX），说明没有找到任何山形三元组，返回-1；否则返回找到的最小和}
};
耗时≈一小时 明天继续