你有一些长度为正整数的木棍。这些长度以数组 sticks 的形式给出， sticks[i] 是第 i 个木棍的长度。
你可以通过支付 x + y 的成本将任意两个长度为 x 和 y 的木棍连接成一个木棍。你必须连接所有的木棍，直到剩下一个木棍。
返回以这种方式将所有给定的木棍连接成一个木棍的 最小成本 。
链接：https://leetcode.cn/problems/minimum-cost-to-connect-sticks/description/
class Solution {public:int connectSticks(vector<int>& sticks) {int res = 0;priority_queue<int, vector<int>, greater<int>> q;for (int i = 0; i < sticks.size(); i++) {q.push(sticks[i]);}while (q.size() > 1) {int stick1 = q.top();q.pop();int stick2 = q.top();q.pop();int cost = stick1 + stick2;res += cost;q.push(cost);}return res;}};
给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/meeting-rooms-ii/description/
class Solution {public:/*** @param intervals: an array of meeting time intervals* @return: the minimum number of conference rooms required*/bool static cmp(Interval& a, Interval& b) {return a.start < b.start || (a.start == b.start && a.end < b.end);}int minMeetingRooms(vector<Interval> &intervals) {if (intervals.empty()) return 0;priority_queue<int, vector<int>, greater<int>> q;sort(intervals.begin(), intervals.end(), cmp);q.push(intervals[0].end);for (int i = 1; i < intervals.size(); ++i) {// if (intervals[i].start > q.top()) {if (intervals[i].start >= q.top()) {q.pop();}q.push(intervals[i].end);}return q.size();}};
中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
例如：
[2,3,4]，中位数是 3
[2,3]，中位数是 (2 + 3) / 2 = 2.5
给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sliding-window-median/description/
一开始就调整好堆大小，然后删掉哪个里面的就加到那个里面就行了。
class Solution {public:vector<double> medianSlidingWindow(vector<int> &nums, int k) {vector<double> result;int n = nums.size();if (n == 0)return result;multiset<int> max, min;for (int i = 0; i < k; ++i) {max.insert(nums[i]);}for (int i = 0; i < k / 2; ++i) {min.insert(*max.rbegin());max.erase(max.lower_bound(*max.rbegin()));}for (int i = k; i < n; ++i) {if (max.size() > min.size())result.push_back(*max.rbegin());else result.push_back(*min.begin() / 2.0 + *max.rbegin() / 2.0);if (max.find(nums[i - k]) != max.end()) {max.erase(max.find(nums[i - k]));max.insert(nums[i]);} else {min.erase(min.find(nums[i - k]));min.insert(nums[i]);}if (!min.empty() && !max.empty() && *min.begin() < *max.rbegin()) {int tmp = *max.rbegin();max.erase(max.lower_bound(*max.rbegin()));max.insert(*min.begin());min.erase(min.begin());min.insert(tmp);}}if (max.size() > min.size())result.push_back(*max.rbegin());else result.push_back(*min.begin() / 2.0 + *max.rbegin() / 2.0);return result;}};
【407. 接雨水 II】
给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/trapping-rain-water-ii/description/
先确定木桶的外围，找到外围的最短板子后对其周围能填水的地方填水，然后更新木桶外围。
class Solution {public:int trapRainWater(vector<vector<int>>& heightMap) {priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,greater<tuple<int, int, int>>> q;int n = heightMap.size();int m = heightMap[0].size();int res = 0;vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};vector<vector<int>> visited(n, vector<int>(m, false));for (int i = 0; i < n; ++i) {q.emplace(heightMap[i][0], i, 0);visited[i][0] = true;q.emplace(heightMap[i][m - 1], i, m - 1);visited[i][m - 1] = true;}for (int i = 0; i < m; ++i) {q.emplace(heightMap[0][i], 0, i);visited[0][i] = true;q.emplace(heightMap[n - 1][i], n - 1, i);visited[n - 1][i] = true;}while (!q.empty()) {int val, x, y;tie(val, x, y) = q.top();q.pop();for (int i = 0; i < 4; ++i) {int nx = x + dir[i][0];int ny = y + dir[i][1];if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {int nh = max(heightMap[nx][ny], val);res += nh - heightMap[nx][ny];q.emplace(nh, nx, ny);visited[nx][ny] = true;}}}return res;}};
关于互联网持续学习圈
