121.买卖股票的最佳时机

描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

分析

利润 = 卖出价格 - 买入价格
遍历迭代最低买入价格
不能在买入前卖出

解答

  int maxProfit(vector<int>& prices) {
    int ans = 0, min_val = prices[0];
    for (auto val : prices) {
      ans = max(ans, val - min_val);
      min_val = min(min_val, val);
    }
    return ans;
  }

135.分发糖果

描述

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子中，评分更高的那个会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

分析

所有孩子皆拥有 1 个
从左向右遍历，若评分比前面高，则更新糖果数
从右向左遍历，若评分比后面高，且糖果数不满足条件则更新糖果数

解答

  int candy(vector<int>& ratings) {
    int len = ratings.size();
    if (len < 2) return len;
    vector<int> nums(len, 1);
    for (int i = 1; i < len; ++i) {
      if (ratings[i] > ratings[i - 1]) {
        nums[i] = nums[i - 1] + 1;
      }
    }
    for (int i = len - 2; i >= 0; --i) {
      if (ratings[i] > ratings[i + 1]) {
        nums[i] = max(nums[i + 1] + 1, nums[i]);
      }
    }
    return accumulate(nums.begin(), nums.end(), 0);
  }

406.根据身高重建队列

描述

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [h_i, k_i] 表示第 i 个人的身高为 h_i ，前面正好有 k_i 个身高大于或等于 h_i 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [h_j, k_j] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

分析

按身高从高到低排序，身高相同则按前后位置排序
按照高个子的位序插入队列
高个子的位序不受矮个子的位序影响

解答

  vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    int len = people.size();
    sort(people.begin(), people.end(), [](vector<int> a, vector<int> b) {
      return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
    });
    vector<vector<int>> tmp;
    for (auto val : people) {
      tmp.insert(tmp.begin() + val[1], val);
    }
    return tmp;
  }

435.无重叠区间

描述

给定一个区间的集合 intervals ，其中 intervals[i] = [start_i, end_i] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

注意只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

分析

按照右侧边界进行排序
一个区间左侧边界小于前一区间右侧边界则区间重叠
迭代右侧边界

解答

  int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    if (intervals.empty()) return 0;
    sort(intervals.begin(), intervals.end(),
         [](vector<int> a, vector<int> b) { return a[1] < b[1]; });
    int total = 0, prev = intervals[0][1];
    for (int i = 1; i < intervals.size(); ++i) {
      if (intervals[i][0] < prev) {
        ++total;
      } else {
        prev = intervals[i][1];
      }
    }
    return total;
  }

452.用最少数量的箭引爆气球

描述

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中 points[i] = [x_start, x_end] 表示水平直径在 x_start 和 x_end之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x_start_，x_end_，且满足 x_start ≤ x ≤ x_end_，则该气球会被引爆 _。可以射出的弓箭的数量 没有限制 。弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，*返回引爆所有气球所必须射出的最小弓箭数 *。

分析

按照区间左侧边界排序
左侧区间小于前一区间的右侧边界则存在区间重叠
未重叠则弓箭数加一，更新下一边界

解答

int findMinArrowShots(vector<vector<int>>& points) {
    sort(points.begin(), points.end(),
         [](vector<int> a, vector<int> b) { return a[0] < b[0]; });
    int count = 1;
    int pre = points[0][1];
    for (int i = 1; i < points.size(); ++i) {
      if (points[i][0] <= pre) {
        pre = min(pre, points[i][1]);
      } else {
        pre = points[i][1];
        count++;
      }
    }
    return count;
  }

455.分发饼干

描述

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。

分析

将孩子和饼干进行排序
依次匹配

解答

  int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int i = 0, j = 0;
    int glen = g.size();
    int slen = s.size();
    while (i < glen && j < slen) {
      if (g[i] <= s[j]) {
        i++;
      }
      j++;
    }
    return i;
  }

605.种花问题

描述

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n ****朵花？能则返回 true ，不能则返回 false 。

分析

满足 000 则可以种一朵化
数组首尾各补一个 0 使得全部元素适用上述规则
遍历

解答

  bool canPlaceFlowers(vector<int>& flowerbed, int n) {
    flowerbed.insert(flowerbed.begin(), 0);
    flowerbed.push_back(0);
    int len = flowerbed.size();
    int count = 0;
    int flag = -1;
    for (int i = 1; i < len - 1; ++i) {
      if (flowerbed[i] == 0 && flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
        flowerbed[i] = 1;
        count++;
      }
    }
    return count >= n;
  }

665.非递减数列

描述

给你一个长度为 n 的整数数组 nums ，请你判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的：对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

分析

nums[i] <= nums [i +1]，不满足则记录
最多只允许存在 1 个不满足点
不满足点位于首尾可以直接修改
不满足点位于中间则分别考虑
- nums[i] 减小，需满足 nums[i-1] <= nums[i+1]
- nums[i+1]增大，需满足 nums[i] <= nums[i +2]

解答

  bool checkPossibility(vector<int>& nums) {
    int len = nums.size();
    int count = 0;
    int idx = -1;
    for (int i = 0; i < len - 1; ++i) {
      if (nums[i] > nums[i + 1]) {
        count++;
        idx = i;
      }
      if (count > 1) return false;
    }
    if (count < 1)
      return true;
    else if (idx == 0 || idx == len - 2)
      return true;
    else
      return (nums[idx - 1] <= nums[idx + 1]) || (nums[idx] <= nums[idx + 2]);
  }

763.划分字母区间

描述

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

分析

题意为相同字符需在同一片段，即区间重叠问题
记录字符的结束区间
将区间存在重叠的字符分划为同一片段

解答

  vector<int> partitionLabels(string s) {
    int n = s.size();
    int last[26];
    for (int i = 0; i < n; ++i) {
      last[s[i] - 'a'] = i;
    }
    vector<int> ans;
    int start = 0, end = 0;
    for (int i = 0; i < n; i++) {
      end = max(end, last[s[i] - 'a']);
      if (end == i) {
        ans.push_back(end - start + 1);
        start = i + 1;
      }
    }
    return ans;
  }