LeetCode Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Given an array of integers nums and an integer limit, return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to limit.

In case there is no subarray satisfying the given condition return 0.

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2
Explanation: All subarrays are:
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4.
Therefore, the size of the longest subarray is 2.


Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.


Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3


Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= limit <= 10^9

class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
int n = nums.size();
int ans = 1; // 最小值是1

for (int i = 0; i < n; ++i) {
vector<int> dp_max(n, 0), dp_min(n, INT_MAX);
dp_max[i] = dp_min[i] = nums[i];
for (int len = 2; len <= n; ++len) {
int j = i + len - 1;
if (j >= n)break;
dp_max[j] = max(dp_max[j - 1], nums[j]);
dp_min[j] = min(dp_min[j - 1], nums[j]);
int diff = dp_max[j] - dp_min[j];
if (diff <= limit) {
ans = max(ans, j - i + 1);
}
else {
break;
}
}
}
return ans;
}
};

class Solution {
public:
int longestSubarray(vector<int>& A, int limit) {
int res = 0, n = A.size(), i = 0, j;
multiset<int> m;
for (j = 0; j < n; ++j) {
m.insert(A[j]);
if (*m.rbegin() - *m.begin() > limit)
m.erase(m.find(A[i++]));
else
res=max(res,j-i+1);
}
return res;
}
};

LeetCode Last Stone Weight

1046. Last Stone Weight

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together.  Suppose the stones have weights x and y with x <= y.  The result of this smash is:

• If x == y, both stones are totally destroyed;
• If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.)

Example 1:

Input: [2,7,4,1,8,1]
Output: 1
Explanation:
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

Note:

1. 1 <= stones.length <= 30
2. 1 <= stones[i] <= 1000

class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int,vector<int>,std::less<int>> pq(stones.begin(),stones.end());
while (pq.size() >= 2) {
int first = pq.top();
pq.pop();
int second = pq.top();
pq.pop();

if (first != second)pq.push(first - second);
}
if (pq.size() == 0)return 0;
else return pq.top();
}
};

LeetCode Maximum Performance of a Team

There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers.

Example 1:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation:
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.


Example 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.


Example 3:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72


Constraints:

• 1 <= n <= 10^5
• speed.length == n
• efficiency.length == n
• 1 <= speed[i] <= 10^5
• 1 <= efficiency[i] <= 10^8
• 1 <= k <= n

class Solution {
public:
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
vector<pair<int, int>> workers;
for (int i = 0; i < n; ++i) {
workers.push_back(make_pair(efficiency[i], speed[i]));
}
sort(workers.begin(), workers.end()); // 默认对pair.first升序排列
priority_queue <int, vector<int>, greater<int> > pq; // pq默认是最大堆，这是构建最小堆
long long ans = 0;
long long sum_speed = 0;
for (int i = n - 1; i >= 0; --i) {
sum_speed += workers[i].second;
pq.push(workers[i].second);
if (pq.size() > k) {
sum_speed -= pq.top();
pq.pop();
}
ans = max(ans, sum_speed*workers[i].first);
}
return ans % (int)(1e9 + 7);
}
};

LeetCode Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

typedef struct Node {
ListNode* ln;
int idx;
bool operator<(const Node& p) const { return this->ln->val < p.ln->val; }
bool operator>(const Node& p) const { return this->ln->val > p.ln->val; }
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists)
{
ListNode *ans = new ListNode(0), *head = ans;
vector<Node> vn;
for (int i = 0; i < lists.size(); i++) {
if (lists[i] != NULL) {
Node nd;
nd.ln = lists[i];
nd.idx = i;
vn.push_back(nd);
lists[i] = lists[i]->next;
}
}
if (vn.size() == 0)
return NULL;
make_heap(vn.begin(), vn.end(), greater<Node>());
while (true) {
Node tmp = vn.front();
ans->next = tmp.ln;
ans = ans->next;
pop_heap(vn.begin(), vn.end(), greater<Node>());
vn.pop_back();
if (lists[tmp.idx] != NULL) {
tmp.ln = lists[tmp.idx];
vn.push_back(tmp);
push_heap(vn.begin(), vn.end(), greater<Node>());
lists[tmp.idx] = lists[tmp.idx]->next;
}
if (vn.empty())
break;
}
}
};

struct LNNode {
ListNode* ln;
LNNode() :ln(NULL) {};
bool operator<(const LNNode& ln_) const{ // 注意两个const都不能少
return ln->val > ln_.ln->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<LNNode> pq;
for (int i = 0; i < lists.size(); ++i) {
if (lists[i] != NULL) {
LNNode cur;
cur.ln = lists[i];
pq.push(cur);
}
}
ListNode* root = new ListNode(0);
ListNode* ans = root;
while (!pq.empty()) {
LNNode cur = pq.top();
pq.pop();
root->next = cur.ln;
root = root->next;
if (cur.ln->next) {
LNNode nxt;
nxt.ln = cur.ln->next;
pq.push(nxt);
}
}
return ans->next;
}
};

struct cmp {
bool operator()(ListNode* l1, ListNode* l2) {
return l1->val > l2->val;
}
};

class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
for (int i = 0; i < lists.size(); ++i) {
if (lists[i] != NULL) {
pq.push(lists[i]);
}
}
ListNode* root = new ListNode(0);
ListNode* ans = root;
while (!pq.empty()) {
ListNode* cur = pq.top();
pq.pop();
root->next = cur;
root = root->next;
if (cur->next) {
pq.push(cur->next);
}
}
return ans->next;
}
};