Leetcode1793. Maximum Score of a Good Subarray

2023-10-24 08:44

本文主要是介绍Leetcode1793. Maximum Score of a Good Subarray,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

给定一个数组和一个下标 k k k

子数组 ( i , j ) (i,j) (i,j)分数定义为 min ⁡ ( n u m s [ i ] , n u m s [ i + 1 ] , ⋯ , n u m s [ j ] ) ∗ ( j − i + 1 ) \min\left(nums[i], nums[i +1],\cdots, nums[j]\right)*\left(j-i+1\right) min(nums[i],nums[i+1],,nums[j])(ji+1)
其中 i ≤ k ≤ j i\le k \le j ikj

找到最大的子数组分数

其实这题有点像是接雨水那个题目

k k k出发,哪一边大就往哪一边扩展

class Solution {
public:int maximumScore(vector<int>& nums, int k) {int n = nums.size();int left = k;int right = k;int ans = nums[k];int cur = nums[k];while(left > 0 || right < n - 1){if((left > 0 ? nums[left - 1]: 0) < (right < n - 1? nums[right + 1]: 0)){++right;cur = min(cur, nums[right]);}else{--left;cur = min(cur, nums[left]);}ans = max(ans, cur * (right - left + 1));}return ans;}
};

时间复杂度 O ( n ) O(n) O(n)

这篇关于Leetcode1793. Maximum Score of a Good Subarray的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/274024

相关文章

856. Score of Parentheses

856. Score of Parentheses class Solution:def scoreOfParentheses(self, s: str) -> int:stack=[]i=0for c in s:if c=='(':stack.append(c)else:score=0while stack[-1]!='(':score+=stack.pop()stack.pop()score

【UVA】1619-Feel Good(数据结构-栈)

既然所有数都是大于等于0的,那么在一个区间最小值一定的情况下,这个区间越长越好(当然有特殊情况) 对一个数a[i],left[i]代表左边第一个比它小的,right[i]代表右边第一个比它小的 如何构造left[i]呢?,从左往右构造一个单调递增的栈(一定是单调的!) 当a[i]比栈顶元素小的时候,栈顶元素出栈,(否则的话入栈,left[i]就是栈顶元素的位置,right数组同理可得

leetcode#628. Maximum Product of Three Numbers

题目 Given an integer array, find three numbers whose product is maximum and output the maximum product. Example 1: Input: [1,2,3]Output: 6 Example 2: Input: [1,2,3,4]Output: 24 Note: The lengt

Maximum likelihood function maximizes what thing?

最大似然函数(Maximum Likelihood Function)最大化的是数据在给定参数下出现的概率。具体来说,它最大化的是似然函数(Likelihood Function),即给定参数 ( \theta ) 下观测数据的概率。在统计学中,似然函数 ( L(\theta) ) 通常定义为所有独立观测数据点概率的乘积,对于参数 ( \theta ) 的函数。 对于一组独立同分布的观测数据

ORA-24067: exceeded maximum number of subscribers for queue ADMIN.SMS_MT_QUEUE

临时处理办法: delete from aq$_ss_MT_tab_D;delete from aq$_ss_MT_tab_g;delete from aq$_ss_MT_tab_h;delete from aq$_ss_MT_tab_i;delete from aq$_ss_MT_tab_p;delete from aq$_ss_MT_tab_s;delete from aq$

Elasticsearch func_score

场景介绍 衰减函数 总结 官网文档:https://www.elastic.co/guide/en/elasticsearch/reference/7.x/query-dsl-function-score-query.html 作者公众号: 1.场景介绍 在全文检索中,排序是一个很讲究的事。关键字命中,是全文检索中一个很关键的因素。然而,某些时候,我们关键字的命中可能非常低,或者来两个

[LeetCode] 239. Sliding Window Maximum

题:https://leetcode.com/problems/sliding-window-maximum/description/ 题目 Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You

vue3 el-menu 菜单Maximum recursive updates exceeded 报错

vue3 用el-menu实现管理后台左侧菜单,报Uncaught (in promise) Maximum recursive updates exceeded in component <ElMenu>. This means you have a reactive effect that is mutating its own dependencies and thus recursivel

CodeForces 451D Count Good Substrings

题意: 一个只包含a和b的字符串  问  它有几个长度为偶数和长度为奇数的“压缩回文串”  压缩的概念是  相邻的相同字符压缩成一个字符 思路: 串经过压缩一定满足如下形式 ……ababab……  那么这样只要两端的字符相同则中间一定是回文的  因此对于一个a它作为左端点形成的回文串个数就等于它右边的a的个数  那么长度是奇数还是偶数呢  可以这么判断  如果a在奇数位置上和它匹配的a也在奇

浙大数据结构:01-复杂度2 Maximum Subsequence Sum

数据结构MOOC PTA习题 01-复杂度2 Maximum Subsequence Sum #include <iostream>using namespace std;const int M = 100005;int a[M];int main(){int k;cin >> k;int f = 1;for (int i = 0; i < k; i++){cin >> a[i