→ Rushia: 大師 03/29 16:25
推 digua: 大師 03/29 16:25
推 SecondRun: 大師 03/29 16:26
→ DJYOSHITAKA: 大濕 03/29 16:42
推 JIWP: 大師 03/29 17:53
2962. Count Subarrays Where Max Element Appears at Least K Times
Solved
Medium
Topics
Companies
You are given an integer array nums and a positive integer k.
Return the number of subarrays where the maximum element of nums appears at leas
t k times in that subarray.
A subarray is a contiguous sequence of elements within an array.
Example 1:
Input: nums = [1,3,2,3,3], k = 2
Output: 6
Explanation: The subarrays that contain the element 3 at least 2 times are: [1,3
,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3] and [3,3].
解法：
因為要找最大的數字
所以一開始就直接找會比較方便
然後再用1來表示的話也會比較方便
然後把經過的出現過的index記錄下來
然後一定要出現k個以上的index
然後就可以利用紀錄過的index
算出有幾種子陣列可以那個了
姆咪
class Solution {
public:
long long countSubarrays(vector<int>& nums, int k)
{
long long res = 0;
int maxn = 0;
int len = nums.size();
for(int i = 0 ; i < len ; i ++)
{
maxn = max(maxn,nums[i]);
}
vector<int> paper(len , 0);
for(int i = 0 ; i < len ; i ++)
{
if(nums[i] == maxn)
{
paper[i] = 1;
}
}
vector<int> save;
int r = 0 ;
for(; r < len ; r ++)
{
if(paper[r])
{
save.push_back(r);
}
if(save.size() >= k)
{
res += save[save.size() - k] + 1;
}
}
return res;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 134.208.57.64 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1711700451.A.A5A.html