代码编织梦想

题目截图

在这里插入图片描述

题目分析

  • 无脑单调栈左右找更大
  • 注意一边不取等,一边取等,避免重复
  • 找到包含当前元素为最大值的区间个数,左 * 右即可

python

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left_: int, right_: int) -> int:
       # 单调栈
        n = len(nums)
        # 左边比自己大的最近的位置
        left, st = [-1] * n, []
        for i, v in enumerate(nums):
            while st and nums[st[-1]] < v: st.pop()
            if st: left[i] = st[-1]
            st.append(i)
        
        # 右边比自己大于等于的最近的位置
        right, st = [n] * n, []
        for i in range(n - 1, -1, -1):
            while st and nums[st[-1]] <= nums[i]: st.pop()
            if st: right[i] = st[-1]
            st.append(i)
        
        # 当前元素作为最大值的区域
        #print(left)
        #print(right)
        ans = 0
        for i in range(n):
            l, r = i - left[i], right[i] - i
            if left_ <= nums[i] <= right_:
                #print(nums[i], l, r)
                ans += l * r
        return ans

java

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        // java单调栈
        int n = nums.length;
        int[] L = new int[n], R = new int[n];
        Arrays.fill(L, -1);
        Arrays.fill(R, n);
        Deque<Integer> st = new ArrayDeque<>();
        // 左边比自己大的最近的位置
        for (int i = 0; i < n; ++i) {
            while (!st.isEmpty() && nums[st.peek()] < nums[i]) st.pop();
            if (!st.isEmpty()) L[i] = st.peek();
            st.push(i);
        }
        // 右边比自己大于等于的最近的位置
        st.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!st.isEmpty() && nums[st.peek()] <= nums[i]) st.pop();
            if (!st.isEmpty()) R[i] = st.peek();
            st.push(i);
        }
        // 当前元素作为最大值的区域
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (left <= nums[i] && nums[i] <= right) {
                ans += (i - L[i]) * (R[i] - i);
            }
        }
        return ans;

    }
}
  • int[] l = new int[n];
  • Deque st = new ArrayDeque<>();
  • st.peak()
  • st.pop()
  • st.push(i)

总结

  • 单调栈无脑
  • 继续熟悉java
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_40986490/article/details/128012231

leetcode 1-100 medium难度题目汇总__eric_lan_的博客-爱代码爱编程_leetcode medium有多少题

写在前面 近半个月的整理, 终于完成了前一百题的easy和medium题目的分析 😅 秋招已经开始了, 祝自己好运 😇 以后有空逐渐把hard补上 😎 文章目录 2. Add Two Numbers (Mediu

LeetCode-数据结构-爱代码爱编程

文章目录 应做未做未弄懂经典题+易错题一、长见识的方法二、杂七杂八积累三、面试常考题目索引java刷题常用树数组摩尔投票算法堆数据流的中位数排序四、基础知识总结4.x 数组前缀和数组前缀和+hash经典题目差分数组树状数组线段树4.x 链表链表反转删除排序链表中的重复元素其他链表相关问题4.1字符串字符串匹配—KMP回文子串马拉车(Manacher

终于等到你,Alibaba首发:大师级算法宝典,足以团灭LeetCode-爱代码爱编程

前言: 说到算法,相信每一个程序员和接触过程序员的朋友都不会陌生,直到现在算法一直占着面试必问的地位,而算法面试也仍是当前最适合公司筛选程序员的方法之一,在阿里,字节跳动、华为等公司带动下,无论是求职者还是面试官,都逐渐认识到算法面试其实是相对高效、准确且公平的筛选机制**,可能你会觉得算法面试有几个实际工作中用到的,不过是“面试造火箭,工作拧螺丝”**

Leetcode——数组和字符串-爱代码爱编程

LeetCode 数组二分法35.搜索插入位置278. 第一个错误的版本724.寻找中心索引前缀和56.合并区间48.旋转图像面试题 01.08. 零矩阵498.对角线遍历(不太好理解)解题思路:代码118. 杨辉三角119. 杨辉三角 II189. 旋转数组217. 存在重复元素(哈希表)136. 只出现一次的数字(位运算)350. 两个数组的交

Java技术类校招面试题汇总:java注解原理解析-爱代码爱编程

第一部分必读系列: 01.学习算法和刷题的思路指南 02.学习数据结构和算法读什么书 03.动态规划解题套路框架 04.动态规划答疑篇 05.动态规划答疑篇 06.回溯算法解题套路框架 07.二分查找解题套路框架 08.滑动窗口解题套路框架 09.双指针技巧总结 10.BFS算法套路框架 11.Linux的进程、线程、文件描述

java二维数组的定义和初始化,面试题+笔记+项目实战-爱代码爱编程

第一部分必读系列: 01.学习算法和刷题的思路指南 02.学习数据结构和算法读什么书 03.动态规划解题套路框架 04.动态规划答疑篇 05.动态规划答疑篇 06.回溯算法解题套路框架 07.二分查找解题套路框架 08.滑动窗口解题套路框架 09.双指针技巧总结 10.BFS算法套路框架 11.Linux的进程、线程、文件描述

【工作感悟】java二维数组的定义和初始化-爱代码爱编程

第一部分必读系列: 01.学习算法和刷题的思路指南 02.学习数据结构和算法读什么书 03.动态规划解题套路框架 04.动态规划答疑篇 05.动态规划答疑篇 06.回溯算法解题套路框架 07.二分查找解题套路框架 08.滑动窗口解题套路框架 09.双指针技巧总结 10.BFS算法套路框架 11.Linux的进程、线程、文件描述

算法学习 (门徒计划)4-2 单调栈(Monotone-Stack)及经典问题 学习笔记-爱代码爱编程

算法学习 (门徒计划)4-2 单调栈(Monotone-Stack)及经典问题 学习笔记 前言单调栈基础性质代码实现总结经典例题LeetCode 155. 最小栈 (基础)解题思路LeetCode 496. 下一个更大元素 I (单调栈的常见应用1)解题思路示例代码LeetCode 503. 下一个更大元素 II (单调栈的常见应用2)解题思路Le

算法周赛笔记(7月第3周)— LeetCode 第57场双周赛-爱代码爱编程

文章目录 题目1941194219431944 这周只参加了一场周赛。先说一下战况,真的太垃圾了,只做出第一题 (ㄒoㄒ) 题目 1941 检查是否所有字符出现次数相同 给你一个字符串 s ,如果 s 是一个 好 字符串,请你返回 true ,否则请返回 false 。 如果 s 中出现过的 所有 字符的出现次数 相同 ,那么我们称字

11.力扣刷题Java-爱代码爱编程

力扣刷题Java 爱学习的饲养员视频内容 https://blog.csdn.net/unspoken0714/article/details/110286517 基础部分: 复杂度 常见的时间复杂度 O(1): 执行常数次,和输入无关 def O1(num): i = num j = num*2 return i+j O(N): d

子数组的最小值之和——单调栈+动态规划-爱代码爱编程

单调栈在解决算法问题时是一个很优化的思路,可以降低时间复杂度。 在接雨水问题——动态规划+单调栈,学习了一道比较经典的单调栈问题,接下来,仍然是对单调栈的一个练习。 1. 题目描述 题目链接:907. 子数组的最小值之和 2. 思路分析 这题意思是,遍历所有的连续子数组,然后求所有子数组中最小值之和。 1)暴力法 遍历所有区间,然后对于每

无重叠区间[贪心练习]_ren_林森的博客-爱代码爱编程

贪心练习 前言一、无重叠区间二、贪心练习总结参考文献 前言 贪心往往代码简单,分析问题比较有难度。尤其是贪心结合单调栈/贪心结合DP都是考察分析能力的好题目。 除此之外,一类时间相关贪心,可以时间为路线;一类是二维数组型的,一般都需要对其中的元素顺序/逆序。当然这些都是套路,训练出自己的抓核心问题的能力,套路不过就是个工具。锻炼寻找核心问题处

字节技术总监耗时半年整理:1000+leetcode刷题笔记(含答案)_java星球的博客-爱代码爱编程

关于算法刷题的困惑和疑问也经常听朋友们提及。这份笔记里面共包含作者刷LeetCode算法题后整理的数百道题,每道题均附有详细题解过程。很多人表示刷数据结构和算法题效率不高,甚是痛苦。有了这个笔记的总结,对校招和社招的算法刷题帮助之大不言而喻,果断收藏了 非常值得一刷的LeetCode题 LeetCode刷题目录 >>附面试思维导图&l

leetcode刷题笔记——剑指offer ii (一)【整数、数组、字符串、链表】_leetcode 剑指offer-爱代码爱编程

目录 整数剑指 Offer II 001. 整数除法剑指 Offer II 002. 二进制加法剑指 Offer II 003. 前 n 个数字二进制中 1 的个数剑指 Offer II 004. 只出现一次

笔试/面试/leetcode刷题经验之谈_笔试形式和leetcode一样吗-爱代码爱编程

  有人相爱,有人夜里开车看海,有人leetcode第一题都做不出来。这是一篇关于leetcode刷题的一点点小心得,如果对你有帮助的话,欢迎点赞转发。 前言 本人以前大学的时候搞过一点算法,但不是什么大佬,学得一般。leetcode只刷了200左右(但都不是啥水题),leetcode简单、中等级别的题目大部分都可以做。大部分公司的笔试题也还行,

数据结构学习笔记 5-爱代码爱编程

喜欢该类型文章可以给博主点个关注,博主会持续输出此类型的文章,知识点很全面,再加上LeetCode的真题练习,每一个LeetCode题解我都写了详细注释,比较适合新手入门数据结构与算法,后续也会更新进阶的文章。 课件参

使数组按非递减顺序排序[问题转换 + dp + 单调栈]_数组移动成非降序-爱代码爱编程

问题转换 + dp + 单调栈 前言一、使数组按非递减顺序排序二、单调栈+问题转换1、思路版2、简洁版 总结参考文献 前言 递减、递增和单调栈紧密相关,单调栈是单调问题的基础。该题可练习预先的

速成算法笔记,github上已收获近60k+star,力压leetcode只为面试_github面试算法-爱代码爱编程

都说程序员工资高、待遇好, 2022 金九银十到了,你的小目标是 30K、40K,还是 16薪的 20K?作为一名 Java 开发工程师,当能力可以满足公司业务需求时,拿到超预期的 Offer 并不算难。然而,提升 Java