NC157. 单调栈
描述
示例1
输入:
[3,4,1,5,6,2,7]
输出:
[[-1,2],[0,2],[-1,-1],[2,5],[3,5],[2,-1],[5,-1]]
示例2
输入:
[1,1,1,1]
输出:
[[-1,-1],[-1,-1],[-1,-1],[-1,-1]]
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-07-18
class Solution {
public:
void foundMonotoneStack(vector<int>& nums, vector<vector<int> >& res,
bool found_back=false) {
stack<int> st;
int index = 0, tx;
if (found_back) {
index = nums.size() - 1;
}
while (index >= 0 && index < nums.size()) {
while (st.size() && nums[st.top()] > nums[index]) {
st.pop();
}
if (st.size()) {
tx = st.top();
}
else {
tx = -1;
}
if (found_back) {
res[index][1] = tx;
}
else {
res[index][0] = tx;
}
st.push(index);
if (found_back) {
--index;
}
else {
++index;
}
}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums intvector
* @return intvector<vector<>>
*/
vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
vector<vector<int> > res;
if (nums.size() < 1) {
return res;
}
res.resize(nums.size());
for (int k = 0; k < res.size(); ++k) {
res[k].resize(2);
}
foundMonotoneStack(nums, res);
foundMonotoneStack(nums, res, true);
return res;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-06-14
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums intvector
* @return intvector<vector<>>
*/
vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
vector<vector<int>>res(nums.size(),vector<int>(2));
stack<int>l,r;
for(int i=0;i<nums.size();i++)
{
int t=nums[i];
if(l.empty())
{
res[i][0]=-1;
}else if(nums[l.top()]<t){
res[i][0]=l.top();
}
else if(nums[l.top()]>=t){
while (!l.empty() && nums[l.top()]>=t){
l.pop();
}
res[i][0]=(l.empty()?-1:l.top());
}
l.push(i);
}
for(int j=nums.size()-1;j>=0;j--)
{
int t=nums[j];
if(r.empty())
{
res[j][1]=-1;
}else if(nums[r.top()]<t){
res[j][1]=r.top();
}
else if(nums[r.top()]>=t){
while (!r.empty() && nums[r.top()]>=t){
r.pop();
}
res[j][1]=(r.empty()?-1:r.top());
}
r.push(j);
}
return res;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-06-14
class Solution {
public:
vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
// 找出arr[i]左右最近的小于arr[i]的位置，不存在则为-1
// [3,4,1,5,6,2,7]
// [[-1,2],[0,2],[-1,-1],[2,5],[3,5],[2,-1],[5,-1]]
// 时间复杂度O(n);空间复杂度O(n),辅助栈
vector<vector<int>> sets(nums.size(),vector<int>(2,0));
stack<int> left,right;
for(int i=0;i<nums.size();++i) {
// 单调栈存放<nums[i]的数据，且单调递增
// 如果nums[i]<nums[stack.top()]，弹出元素直到栈为空或小于等于nums[i]，此时栈顶位置就是最近的<nums[i]的位置
// (如果栈中被弹出的元素是>nums[i]的，那么对于之后的<nums[i]的数，这些数据也是要弹出来的；对于之后的>nums[i]的数，nums[i]就是最近的元素了)
//
// 3
// 3,4
// 1
// 1,5
// 1,5,6
// 1,2
// 1,2,7
while(!left.empty() && nums[left.top()]>nums[i]) {
left.pop();
}
if( left.empty() ) {
sets[i][0]=-1;
}
else {
sets[i][0] = left.top();
}
left.push(i);
}
for(int i=nums.size()-1;i>=0;--i) {
while(!right.empty() && nums[right.top()]>nums[i]) {
right.pop();
}
if( right.empty() ) {
sets[i][1]=-1;
}
else {
sets[i][1] = right.top();
}
right.push(i);
}
return sets;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-06-14
const int N = 1e5 + 10;
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums intvector
* @return intvector<vector<>>
*/
int q[N];
int tt = 0;
vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
// write code here
int n = nums.size();
vector<vector<int>> res;
for(int i = 0; i < n; i ++){
while(tt > 0 && nums[q[tt]] >= nums[i]) tt --;
if(tt > 0) res.push_back({q[tt]});
else res.push_back({-1});
q[++ tt] = i;
}
tt = 0;
for(int i = n -1; i >= 0; i --){
while(tt > 0 && nums[q[tt]] >= nums[i]) tt --;
if(tt > 0) res[i].push_back(q[tt]);
else res[i].push_back(-1);
q[++ tt] = i;
}
return res;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-04-30
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums intvector
* @return intvector<vector<>>
*/
vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
// write code here
vector<int> leftRec( nums.size() );
vector<int> rightRec(nums.size());
stack<int> cStack;
leftRec[0] = -1;
cStack.push(0);
for(int i=1; i<nums.size(); i++)
{
//nums[i] <=
while( !cStack.empty() && nums[cStack.top()] >= nums[i] )
{
cStack.pop();
}
if( cStack.empty() )
{
leftRec[i] = -1;
}
else
{
leftRec[i] = cStack.top();
}
cStack.push(i);
}
rightRec[ nums.size()-1 ] = -1;
stack<int> cStack2;
cStack2.push( nums.size()-1 );
for(int i=nums.size()-2; i>=0; i--)
{
//nums[i] <=
while( !cStack2.empty() && nums[cStack2.top()] >= nums[i] )
{
cStack2.pop();
}
if( cStack2.empty() )
{
rightRec[i] = -1;
}
else
{
rightRec[i] = cStack2.top();
}
cStack2.push(i);
}
vector<vector<int>> rst;
for(int i=0; i<nums.size(); i++)
{
vector<int> tmp;
tmp.push_back(leftRec[i]);
tmp.push_back(rightRec[i]);
rst.push_back(tmp);
}
return rst;
}
};