daimayuan#436. 子串的最大差(单调栈)

简介: daimayuan#436. 子串的最大差(单调栈)
/*********************************************************************
    程序名:
    版权: Joecai
    作者: Joecai
    日期: 2022-04-30 00:10
    说明:
*********************************************************************/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
# define rep(i,be,en) for(int i=be;i<=en;i++)
# define pre(i,be,en) for(int i=be;i>=en;i--)
#define ll long long
#define endl "\n"
#define LOCAL
#define pb push_back
#define int long long
typedef pair<ll, ll> PII;
#define eb emplace_back
#define sp(i) setprecision(i)
const int N = 5e5 + 10, INF = 0x3f3f3f3f;
int n;
int a[N];
stack<int>s;
int l1[N];//左边区间的最大值
int l2[N];
int r1[N];//右边区间的最小值
int r2[N];
void solve()
{
  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) //单调递减的栈 左闭右开防止被选两次
  {
    while (s.size() && a[s.top()] <= a[i]) s.pop();
    if (s.size() == 0)
    {
      l1[i] = i;
    } else
    {
      l1[i] = i - s.top();
    }
    s.push(i);
  }
  while (s.size()) s.pop();
  for (int i = n; i >= 1; i--)
  {
    while (s.size() && a[s.top()] < a[i]) s.pop();
    if (s.size() == 0)
    {
      r1[i] = n - i + 1;
    } else
    {
      r1[i] = s.top() - i;
    }
    s.push(i);
  }
  while (s.size()) s.pop();
  for (int i = 1; i <= n; i++)
  {
    while (s.size() && a[s.top()] >= a[i]) s.pop();
    if (s.size())
    {
      l2[i] = i - s.top();
    } else
    {
      l2[i] = i;
    }
    s.push(i);
  }
  while (s.size()) s.pop();
  for (int i = n; i >= 1; i--)
  {
    while (s.size() && a[s.top()] > a[i]) s.pop();
    if (s.size())
    {
      r2[i] = s.top() - i;
    } else
    {
      r2[i] = n - i + 1;
    }
    s.push(i);
  }
  int ans = 0;
  for (int i = 1; i <= n; i++)
  {
    ans += a[i] * ((l1[i]) * (r1[i]) - (l2[i]) * (r2[i]));
  }
  cout << ans << endl;
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  //#ifdef LOCAL
  //freopen("data.in.txt","r",stdin);
  //freopen("data.out.txt","w",stdout);
  //#endif
  int __ = 1;
  //cin>>__;
  while (__--)
  {
    solve();
  }
  return 0;
}
目录
相关文章
|
9天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
75 9
|
2天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
5天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
7天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
30 4
|
12天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
25天前
数据结构(栈与列队)
数据结构(栈与列队)
16 1
|
29天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
63 1
|
26天前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
13 0
|
30天前
探索顺序结构:栈的实现方式
探索顺序结构:栈的实现方式
|
30天前
|
存储 C语言
栈和队列题目练习
栈和队列题目练习
16 0
下一篇
无影云桌面