中国煤炭建设协网站,设计建设网站公司,西安seo交流,网站设计要点 优帮云84. 柱状图中最大的矩形
题目地址#xff1a;84. 柱状图中最大的矩形 - 力扣#xff08;LeetCode#xff09;
题解思路#xff1a;暴力#xff1a;每一列记为矩形的高#xff0c;找左边和右边比他小的位置#xff0c;得到以该列为高对应的宽#xff1b;这样最大的矩形…84. 柱状图中最大的矩形
题目地址84. 柱状图中最大的矩形 - 力扣LeetCode
题解思路暴力每一列记为矩形的高找左边和右边比他小的位置得到以该列为高对应的宽这样最大的矩形 max(每一列为高 * 对应的宽)
优化思路单调栈递减栈暴力中找左右的过程可以进行预处理单调栈记录某一列左/右第一个比他小的位置cur指向右边第一个小的位置stk.top指向该列stk.top-1指向左边第一个小的位置
时间复杂度O(n)
空间复杂度O(n)
代码:
class Solution {
public:int largestRectangleArea(vectorint heights) {int ret 0; // 前后需要哨兵heights.insert(heights.begin(), 0);heights.emplace_back(0);int size heights.size();stackintstk;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 ∗ k C^k_n * k Cnk∗k)组合数然后每次记录emplace_back用k
空间复杂度O(n)递归
代码:
class Solution {
public:vectorvectorintret;vectorintpath;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();}}vectorvectorint combine(int n, int k) {// 回溯树形结构从左到右// 确定返回类型和参数类型终止条件单层逻辑backtrack(n, k, 1);return ret;}
};216. 组合总和 III
题目地址216. 组合总和 III - 力扣LeetCode
题解思路回溯如注释
时间复杂度O( C n k ∗ k C^k_n * k Cnk∗k)组合数然后每次记录emplace_back用k
空间复杂度O(n)递归
代码:
class Solution {
public:vectorvectorintret;vectorintpath;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();}}vectorvectorint combinationSum3(int k, int n) {backtrack(k, n, 1, 0);return ret;}
};
