temperatures
, return an array answer
such that answer[i]
is the number of days you have to wait after the ith
day to get a warmer temperature. answer[i] == 0
instead.Example 1:
Example 2:
Example 3:
1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100
/**
* @param {number[]} temperatures
* @return {number[]}
*/
var dailyTemperatures = function(temperatures) {
const totalLength = temperatures.length;
const answer = new Array(totalLength).fill(0);
const stack = [];
for (let i = 0; i < totalLength; i++) {
while (stack.length && temperatures[stack[stack.length - 1]] < temperatures[i]) {
const index = stack.pop();
answer[index] = i - index;
}
stack.push(i);
}
return answer;
};
Given a balanced parentheses string s
, return the score of the string.
The score of a balanced parentheses string is based on the following rule:
"()"
has score 1
.AB
has score A + B
, where A
and B
are balanced parentheses strings.(A)
has score 2 * A
, where A
is a balanced parentheses string.Example 1:
Example 2:
Example 3:
2 <= s.length <= 50
s
consists of only '('
and ')'
.s
is a balanced parentheses string./**
* @param {string} s
* @return {number}
*/
var scoreOfParentheses = function(s) {
const stack = [0];
const closeParentheses = ')';
for (let i = 0; i < s.length; i++) {
if (s[i] === closeParentheses) {
let last = stack.pop();
last = last === 0 ? 1 : last * 2;
stack[stack.length - 1] += last;
} else {
stack.push(0);
}
}
return stack[stack.length - 1];
};
n
가로길이가 m
인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.시추관의 위치 | 획득한 덩어리 | 총 석유량 |
---|---|---|
1 | [8] | 8 |
2 | [8] | 8 |
3 | [8] | 8 |
4 | [7] | 7 |
5 | [7] | 7 |
6 | [7] | 7 |
7 | [7, 2] | 9 |
8 | [2] | 2 |
오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.
석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land
가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.
land
의 길이 = 땅의 세로길이 = n
≤ 500land[i]
의 길이 = 땅의 가로길이 = m
≤ 500land[i][j]
는 i+1
행 j+1
열 땅의 정보를 나타냅니다.land[i][j]
는 0
또는 1
입니다.land[i][j]
가 0
이면 빈 땅을, 1
이면 석유가 있는 땅을 의미합니다.land
의 길이 = 땅의 세로길이 = n
≤ 100land[i]
의 길이 = 땅의 가로길이 = m
≤ 100시추관의 위치 | 획득한 덩어리 | 총 석유량 |
---|---|---|
1 | [12] | 12 |
2 | [12] | 12 |
3 | [3, 12] | 15 |
4 | [2, 12] | 14 |
5 | [2, 12] | 14 |
6 | [2, 1, 1, 12] | 16 |
function solution(land) {
const n = land.length;
const m = land[0].length;
const visited= new Array(n).fill().map(_ => new Array(m).fill(0));
const oilMap = new Map();
let maxOil = 0;
let oilIndex = 1;
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
function bfs(rowIndex, colIndex) {
const queue = [[rowIndex, colIndex]];
let oilCount = 0;
visited[rowIndex][colIndex] = oilIndex;
while(queue.length) {
const [x, y] = queue.shift();
if (land[x][y]) {
oilCount++;
}
for (let i=0; i<4; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny]) continue;
if (land[nx][ny]) {
visited[nx][ny] = oilIndex;
queue.push([nx, ny]);
}
}
}
oilMap.set(oilIndex, oilCount);
oilIndex++;
return oilCount;
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (! visited[i][j]&& land[i][j]) {
bfs(i, j);
}
}
}
for (let colIndex = 0; colIndex < m; colIndex++) {
let oilSum = 0;
const oilIndexSet = new Set();
for(let rowIndex = 0; rowIndex < n; rowIndex++) {
const oilIndex = visited[rowIndex][colIndex];
if (oilIndex) {
if (!oilIndexSet.has(oilIndex)) {
oilSum += oilMap.get(oilIndex);
}
oilIndexSet.add(oilIndex);
}
}
maxOil = Math.max(maxOil, oilSum);
}
return maxOil
}