408算法题leetcode--第28天

84. 柱状图中最大的矩形

题目地址：84. 柱状图中最大的矩形 - 力扣（LeetCode）

题解思路：暴力：每一列记为矩形的高，找左边和右边比他小的位置，得到以该列为高对应的宽；这样最大的矩形 = max(每一列为高 * 对应的宽)

优化思路：单调栈，递减栈：暴力中找左右的过程可以进行预处理，单调栈记录某一列左/右第一个比他小的位置；cur指向右边第一个小的位置，stk.top指向该列，stk.top-1指向左边第一个小的位置

时间复杂度：O(n)

空间复杂度：O(n)

代码:

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int ret = 0; // 前后需要哨兵heights.insert(heights.begin(), 0);heights.emplace_back(0);int size = heights.size();stack<int>stk;stk.push(0);  // 下标for(int i = 1; i < size; i++){if(heights[i] >= heights[stk.top()]){stk.push(i);} else {while(!stk.empty() && heights[i] < heights[stk.top()]){int mid = stk.top();stk.pop();if(!stk.empty()){int left = stk.top();int h = heights[mid];int w = i - left - 1;ret = max(ret, h * w);}}stk.push(i);}}return ret;}
};

77. 组合

题目地址：77. 组合 - 力扣（LeetCode）

题解思路：如注释

时间复杂度：O($C_n^k\ast k$)，组合数，然后每次记录emplace_back用k

空间复杂度：O(n)，递归

代码:

class Solution {
public:vector<vector<int>>ret;vector<int>path;void backtrack(int n, int k, int start){if(path.size() == k){ret.emplace_back(path);return;}// 剪枝，还需要k - path.size()个元素，即下标从n - (k - size) + 1for(int i = start; i <= n - (k - path.size()) + 1; i++){path.emplace_back(i);backtrack(n, k, i + 1);path.pop_back();}}vector<vector<int>> combine(int n, int k) {// 回溯，树形结构，从左到右// 确定返回类型和参数类型；终止条件；单层逻辑backtrack(n, k, 1);return ret;}
};

216. 组合总和 III

题目地址：216. 组合总和 III - 力扣（LeetCode）

题解思路：回溯，如注释

时间复杂度：O($C_n^k\ast k$)，组合数，然后每次记录emplace_back用k

空间复杂度：O(n)，递归

代码:

class Solution {
public:vector<vector<int>>ret;vector<int>path;void backtrack(int k, int n, int start, int sum){if(path.size() == k){if(sum == n){ret.push_back(path);}return ;}// 剪枝1, sum过大；剪枝2，还需要k - size个数字，下标从9 - (k - size) + 1开始if(sum > n){return;}if(start > 9 - (k - path.size()) + 1){return ;} // 单层for(int i = start; i <= 9; i++){path.emplace_back(i);backtrack(k, n, i + 1, sum + i);path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {backtrack(k, n, 1, 0);return ret;}
};