lapt BlogPostsTagsGallerydemogameLeetCode
力扣算法：数据结构
|leetcode

数据结构

  • 栈与队列
    • 单调栈
    • 单调队列
  • 树状数组

链表

  1. dummy head: ListNode* dummyHead = new ListNode()
    (new 用于开辟内存，需要使用指针来接收，需要搭配delete使用)

栈与队列

单调栈

  1. 从当前的下标，从右往左找第一个比它小的值的下标：【递增单调栈】
  2. 从当前的下标，从右往左找第一个比它大的值的下标：【递减单调栈】
  • 递增单调栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
stack<int> sta;
// 遍历当前的数组
for (int i=0; i<arr.size(); i++) {
    // arr[i] <= arr[sta.top()] 等于的情况被弹出
    // arr[i] < arr[sta.top()]  等于的情况保留在栈内
    while (!sta.empty() && arr[i] <= arr[sta.top()]) {
        sta.pop();
    }
    // 此时如果栈不为空，当前栈顶的元素，就是我们要找的元素，第一个比当前元素小的。
    if (!sta.empty()) left[i] = sta.top();
    else left[i] = -1;
    // 把当前元素入栈
    sta.push(i);
}

题目：1 ，2

树状数组

单调队列

leetcode