代码随想录一轮刷题结束：Leetcode503、42、LCR39、48、73

本文主要是介绍代码随想录一轮刷题结束：Leetcode503、42、LCR39、48、73，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode503：

问题描述：

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

示例 1:

输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

示例 2:

输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示:

• 1 <= nums.length <= 104
• -109 <= nums[i] <= 109

代码（单调栈可以存储最近大于或小于改元素的下标）：

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {int n=nums.size();vector<int>ans(n,-1);stack<int>s1;s1.push(0);int last=0;//循环两轮还没找到，肯定不存在比该元素还大的for(int i=1;i<n;i++){while(!s1.empty()&&nums[i]>nums[s1.top()]){ans[s1.top()]=nums[i];s1.pop();}s1.push(i);}for(int i=0;i<n;i++){while(!s1.empty()&&nums[i]>nums[s1.top()]){ans[s1.top()]=nums[i];s1.pop();}}return ans;}
};

Leetcode42：

问题描述：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

代码：

class Solution {
public:int trap(vector<int>& height) {int ans=0;stack<int>s1;for(int i=0;i<height.size();i++){while(!s1.empty()&&height[i]>height[s1.top()]){int top=s1.top();s1.pop();if(s1.empty())break;int left=s1.top();int width=i-left-1;int height1=min(height[left],height[i])-height[top];ans+=width*height1;}s1.push(i);}return ans;}
};

Leetcode39：

问题描述：

给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

代码：

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int n=heights.size();vector<int>leftMax(n,-1);vector<int>rightMax(n,n);stack<int>s1;for(int i=0;i<n;i++){while(!s1.empty()&&heights[i]<heights[s1.top()]){rightMax[s1.top()]=i;s1.pop();}s1.push(i);}while(!s1.empty())s1.pop();for(int i=n-1;i>=0;i--){while(!s1.empty()&&heights[i]<heights[s1.top()]){leftMax[s1.top()]=i;s1.pop();}s1.push(i);}int ans=0;for(int i=0;i<n;i++){int sum=(rightMax[i]-1-leftMax[i])*heights[i];ans=max(ans,sum);}return ans;}
};

Leetcode48：

问题描述：

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

代码：

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n=matrix.size();for(int i=0;i<n/2;i++){for(int j=0;j<(n+1)/2;j++){int temp = matrix[i][j];matrix[i][j] = matrix[n - j - 1][i];matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];matrix[j][n - i - 1] = temp;}}}
};

Leetcode73：

问题描述：

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

代码：

class Solution {
public:int row[205];int col[205];void setZeroes(vector<vector<int>>& matrix) {int n=matrix.size();int m=matrix[0].size();for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(matrix[i][j]==0){row[i]=-1;col[j]=-1;}}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(row[i]==-1||col[j]==-1)matrix[i][j]=0;}}}
};

这篇关于代码随想录一轮刷题结束：Leetcode503、42、LCR39、48、73的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---