はじめに
Neetcodeのロードマップの内、1~17問をコードとともに解説していきます。Neetcodeとは就職・転職の面接を受ける際に出題データ構造とアルゴリズムに関わる問題をまとめたサイトで、アリゴリズム問題をどの順番で解いていくのが良いかというロードマップを提供してくれています。
計算量オーダーについて
アルゴリズムにおける計算量とは、アルゴリズムが問題を解くために必要とする時間やメモリの量を指し、主に2つの観点から評価されます。
時間計算量（Time Complexity）
アルゴリズムが問題を解くのにかかる、実行時間を表します。入力サイズnに対する操作回数の増加具合を表現しています。時間計算量は主にビッグO記法（Big-O Notation）で表され、入力サイズが大きくなったときの最悪ケースの増加率を表します。
| 記法 | 説明 | 例 |
|---|---|---|
| O(1) | 定数時間：入力サイズに依存しない | 配列の特定の要素にアクセスする |
| O(log n) | 対数時間：データが半分に減る | 二分探索 |
| O(n) | 線形時間：データの量に比例 | 配列の全要素を走査 |
| O(n log n) | 準線形時間：効率的なソートアルゴリズム | クイックソート、マージソート |
| O(n²) | 二次時間：二重ループ処理 | バブルソート、選択ソート |
| O(2ⁿ) | 指数時間：非常に非効率 | 全探索（ブレートフォース） |
| O(n!) | 階乗時間：極めて非効率 | 巡回セールスマン問題の全探索 |
※ 巡回セールスマンとは、都市の集合と各2都市間の移動コスト（距離など）を求めるときに、文字通り全てのとりうる経路を調べ上げて、最短経路を求める方法のことを指します。
O(n)の例：配列の全ての要素を1つずつ調べるため、データが増えると実行時間も直線的に増加します。
const linear_search = (arr, target) => {
for (const item in arr) {
if (item === target) {
return true
}
return false
}
}
二分探索（O(log n))の例：ソートされた配列に対して使用し、探索範囲を半分に絞ることで高速に検索します。
const binarySearch => (arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return true;
} else if (arr[mid] < target) {
left = mid + 1; // 右側を探索
} else {
right = mid - 1; // 左側を探索
}
}
return false;
}
空間計算量（Space Complexity）
アルゴリズムが使用するメモリ量の増加具合を表現します。入力サイズnに対して、どれだけの追加メモリが必要かを評価します。
| 記法 | 説明 | 例 |
|---|---|---|
| O(1) | 定数メモリ：固定サイズのメモリ使用 | 変数1つのみ使用 |
| O(n) | 線形メモリ：データサイズに比例 | 新しい配列やリストを作成 |
| O(n²) | 二次メモリ：2次元配列や行列の使用 | 行列の保存や処理 |
O(1)の例：配列の要素をその場で反転します。追加のメモリを使用しないため、空間計算量はO(1)で対応可能です。
const reverseArray = (arr) => {
let left = 0;
let right = arr.length - 1;
while (left < right) {
// 要素を入れ替え
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
return arr;
}
O(n)の例：配列を複製して新しい配列を作成します。元の配列サイズに比例してメモリを使用するため、空間計算量はO(n)となります。
duplicateArray = (arr) => {
return arr.concat(arr); // 元の配列を2回結合
}
1. Contains Duplicate
Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.
数値の配列が与えられる。配列内に重複した値がした場合はtrueを返す。
解答
hasDuplicate(nums) {
const duplicate = new Set()
for (let i = 0; i < nums.length; i++) {
if(duplicate.has(nums[i])) {
return true
}
duplicate.add(nums[i])
}
return false
}
解説
配列内に重複した値があるかどうかを判定する必要があるため、Setオブジェクトを用意して、Setインスタンス内に、同じ値を持つ数値がない場合はオブジェクト内に追加します。また以下のように配列をソートして、隣同士の値を比較するという手段もあります。
hasDuplicate(nums) {
const sortNums = nums.sort((a,b) => a - b)
for (let i = 0; i < sortNums.length; i++) {
if(sortNums[i] === sortNums[i - 1]) {
return true
}
}
return false
}
2. Valid Anagram
Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.
An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.
sとtにそれぞれ文字列型が与えられ、anagram（単語や文字の順番を並べ替えて、全く同じ単語や文字にになるもの）であればtrueを返します。
解答
isAnagram(s, t) {
if (s.length !== t.length) {
return false;
}
return s.split('').sort().join('') === t.split('').sort().join('')
}
解説
sとtの長さが違う場合は、anagramの条件にマッチしないため、falseとします。次に文字列を分割してソートし、再度文字列を連結させることで、anagramかどうかを判定します。
3. Two Sum
Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.
You may assume that every input has exactly one pair of indices i and j that satisfy the condition.
Return the answer with the smaller index first.
整数の配列が格納されたnumsと整数targetが渡されます。nums[i] + nums[j] == targetかつi != jとなった場合の、最初のインデックスをそれぞれ求めます。
解答
twoSum(nums, target) {
const targetArray = new Map()
for (let i = 0; i < nums.length; i++) {
const diff = target - nums[i];
if(targetArray.has(diff)) {
return [targetArray.get(diff), i];
} else {
targetArray.set(nums[i], i)
}
}
return []
}
解説
一番初めに思いつく方法として二重ループ（brute force）が考えられますが、計算量がO(n^2)となります。ハッシュマップ（辞書型）のアプローチを行います。numsを1回だけループさせ、各 numに対して、target - numがすでにmapにあるかを確認します。なければmapにkeyを追加します。時間計算量はループ0(n) + ハッシュマップの探索0(1)で0(n)となります。
4. Group Anagrams
Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order.
An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.
配列のうち、anagram（単語や文字の順番を並べ替えて、全く同じ単語や文字にになるもの）をグループ化してサブリストにまとめます。
解答
groupAnagrams(strs) {
if(!strs.length) return []
const target = new Map();
for (let i = 0; i < strs.length; i++) {
const str = strs[i].split('').sort((a,b) => a.localeCompare(b)).join('')
if(target.has(str)) {
target.get(str).push(strs[i])
} else {
target.set(str, [strs[i]])
}
}
return Array.from(target.values())
}
解説
ハッシュマップを使用して、キーを作成し配列を再度生成します。sort時は、localeCompareを使用して、明確にアルファベット順に並べるように設定し、Array.from(target.values()) でMapの値（配列）を取得します。時間計算量、空間計算量ともにO(n)。
5. Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements within the array.
The test cases are generated such that the answer is always unique.
You may return the output in any order.
整数配列numsと整数が与えられた場合k、k配列内で最も頻繁に出現する要素を返却します。出力は任意の順番で返すことができます。
解答
topKFrequent(nums, k) {
const counts = []
const groupedById = nums.reduce((acc, sec) => {
if (!acc[sec]) {
acc[sec] = []
}
acc[sec].push(sec)
return acc
}, {})
const sortedNums = Object.values(groupedById).sort((a,b) => b.length - a.length)
sortedNums.slice(0, k).map((array) => {
counts.push(array[0])
})
return counts
}
解説
初めに、配列の要素から数値毎に同じかどうか判定し、同じ数値を配列で格納します。
最も頻繁に出現するk個の要素を取得するために、配列の長い順でソート後に.slice(0, k)を行い、各配列の最初の要素を取得します。
6. Encode and Decode Strings
Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list of strings.
Please implement encode and decode
リストの文字列を1つの文字列にエンコードし、その後元のリストにデコードします。
解答
/**
* @param {string[]} strs
* @returns {string}
*/
encode(strs) {
let str = ''
strs.forEach((v) => {
const encode = v.length + '#' + v
str += encode
})
return str
}
/**
* @param {string} str
* @returns {string[]}
*/
decode(str) {
const res = [];
let i = 0;
while (i < str.length) {
let j = i;
while (str[j] !== '#') {
j++;
}
const length = parseInt(str.substring(i, j)); // 例: `4#leet` → `4` を取得
const word = str.substring(j + 1, j + 1 + length); // `#`の次から`length`の分だけ取得
res.push(word);
i = j + 1 + length; // インデックスを更新
}
return res;
}
解説
各文字列の長さを保存し、それを利用して元に戻す処理を行います。エンコード時length + '#' + stringという形式で連結を行います。エンコードされた文字列は"4#leet4#code2#is3#fun"のような形式になっています。
デコード時には、エンコードされた文字列を元のリストに復元する処理を加えます。文字列を走査して、#までの部分を整数として取得。その後#の次の数字から長さ分の文字列を抽出します。
7. Products of Array Except Self
Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i].
Each product is guaranteed to fit in a 32-bit integer.
整数が格納された配列numから、各nums[i]を除いたnumsの全要素の積を求めるという問題です。
解答
class Solution {
/**
* @param {number[]} nums
* @return {number[]}
*/
productExceptSelf(nums) {
const length = nums.length
const res = Array(length).fill(1)
let left = 1
for (let i = 0; i < length; i++) {
res[i] = left
left *= nums[i]
}
let right = 1
for (let i = length - 1; i >= 0; i--) {
res[i] *= right
right *= nums[i]
}
return res
}
}
解説
二重ループのO(n^2)のパターンは非効率的です。二重ループではなく、"左からの積" と "右からの積" を組み合わせる方法を使うと O(n)で解くことが可能です。
8. Valid Sudoku
You are given a a 9 x 9 Sudoku board board. A Sudoku board is valid if the following rules are followed:
Each row must contain the digits 1-9 without duplicates.
Each column must contain the digits 1-9 without duplicates.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without duplicates.
Return true if the Sudoku board is valid, otherwise return false
Note: A board does not need to be full or be solvable to be valid.
9×9のボードがあり、ボードが有効であるために、次のルールを守る必要があります。
- 各行には1から9の数字が重複せずに含まれていなければなりません。
- 各列にも1から9の数字が重複せずに含まれていなければなりません。
- グリッド内の3×3の各小ブロック（全体で9個）にも、1から9の数字が重複せずに含まれていなければなりません。
ボードが有効であればtrueを、そうでなければfalseを返してください。
解答
isValidSudoku(board) {
const rows = Array.from({ length: 9 }, () => new Set());
const cols = Array.from({ length: 9 }, () => new Set());
const boxes = Array.from({ length: 9 }, () => new Set());
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
const val = board[i][j];
if (val === '.') continue;
const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
if (rows[i].has(val) || cols[j].has(val) || boxes[boxIndex].has(val)) {
return false;
}
rows[i].add(val);
cols[j].add(val);
boxes[boxIndex].add(val);
}
}
return true;
}
解説
初回は全くわからなかったので、参考記事やChatGTPでヒントをもらいながら解いていきました。
rows[i]でi行目に出現した数字を記録し、cols[j]でj列目に出現した数字を記録します。boxes[boxIndex]では3×3 枠のインデックスに基づく重複チェック。かなり複雑になりますがmboxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3)で0～8 の枠を特定し、Setを使って重複チェックを行います。
9. Longest Consecutive Sequence
Given an array of integers nums, return the length of the longest consecutive sequence of elements that can be formed.
A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. The elements do not have to be consecutive in the original array.
整数の配列numsが与えられたとき、形成できる最長の連続した要素のシーケンスの長さ（それぞれの要素が前の要素よりちょうど1大きい）を返却します。アルゴリズムはO(n)の時間計算量で動作する必要があります。
解答
longestConsecutive(nums) {
if(!nums.length) return 0
const numSet = new Set(nums)
let length = 0
for(const num of numSet){
if (!numSet.has(num - 1)) {
// 連続する数列の「先頭」であるかどうかを判断する
let currentNum = num
let currentLength = 1
// 整数の配列から連続した数値の長さを計算
while (numSet.has(currentNum + 1)) {
currentNum++;
currentLength++; // シーケンス長さを格納
}
length = Math.max(length, currentLength); // 最大値を格納
}
}
return length
}
解説
まずはすべての数値をSetに格納して、連続する数列の「先頭」であるかどうかを判定します。!numSet.has(num - 1)であれば連続した数値ではないため、先頭と判断でき、整数の配列からnum + 1で連続した数値の長さを計算してlengthに格納します。num - 1を辿って連続した数値の長さを割り出します。num - 1がSetにない場合、currentLengthは1からのカウントになります。最後に現在格納されている数値とcurrentLengthのカウント数を比較して長い方を返すように設定します。
10. Valid Palindrome
Given a string s, return true if it is a palindrome, otherwise return false.
A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.
Palindrome（パリンドローム、回文）であればtrueを返します。
回文は前から読んでも後ろから読んでも同じになる言葉や文のことを指します。
解答
isPalindrome(s) {
const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
let left = 0
let right = cleaned.length - 1
while(left < right){
if(cleaned[right] !== cleaned[left]){
return false
}
left++
right--
}
return true
}
解説
?や!などが入ってきた場合、回文だったとしてもfalseで判定されてしまう為、アルファベット・数値のみを参照するようにします。leftを先頭から、rightを末尾から進めて一致を確認します。
11. Two Integer Sum II
Given an array of integers numbers that is sorted in non-decreasing order.
Return the indices (1-indexed) of two numbers, [index1, index2], such that they add up to a given target number target and index1 < index2. Note that index1 and index2 cannot be equal, therefore you may not use the same element twice.There will always be exactly one valid solution.
Your solution must use O(1) additional space.
順不同の数値が格納されているnumbersと特定の値targetが与えられ、numbersの2つの要素を合計するとtargetになる要素のindexを返すという問題です。有効な値は常に一つであることが想定されます。
解答
class Solution {
twoSum(numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) {
return [left + 1, right + 1]; // 1-indexed
} else if (sum < target) {
left++; // 小さい値を大きくする
} else {
right--; // 大きい値を小さくする
}
}
return [];
}
}
解説
この問題は、ソートされた配列を利用して効率的にターゲットに一致する2つの要素を見つける必要があります。一番最初に思いつくコードは二重ループ（Brute Force）による解法かと思います。外側のループと内側のループを比較して、2つの数値の和がターゲットに一致するかを確認する方法です。
class Solution {
twoSum(numbers, target) {
for (let i = 0; i < numbers.length; i++) {
for(let j = i + 1; j < numbers.length; j++){
if(target === numbers[i] + numbers[j]) {
return [i + 1 , j + 1]
}
}
}
return []
}
}
ただこのコードの時間計算量は O(n²)になります。外側ループがO(n)。内側ループがO(n)（平均して約 n/2回の操作）。結果として、全体の計算量は O(n × n) = O(n²)。
この問題の制約であるO(1)追加空間を考慮すると、「Two Pointers法」が最適解となります。
「Two Pointers法」は主に配列やリスト内の2つの要素のポインタ（位置）を同時に追跡し、それらを独立してまたは一緒に移動させる事で問題を解く方法です。配列の先頭にleft、末尾にrightを配置して、targetに一致するペアが見つかるまで、配列の値を移動させます。今回は「常に解が存在する」ことが問題文の前提となっている為、値が見つからなかった場合の考慮は不要です。
return文で[i + 1 , j + 1]としている理由は、問題文で「1-indexed」のインデックスを要求しているためです。「0-indexed」の場合は、通常の配列通り0からインデックスが始まります。
Two Pointers法の計算量
時間計算量: O(n)（1回のループで解を見つけられる）
空間計算量: O(1)（追加のデータ構造を使用しない）
12. 3Sum
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct.
The output should not contain any duplicate triplets. You may return the output and the triplets in any order.
数値が格納されている変数numsを合計値が0となるような、[nums[i], nums[j], nums[k]]に並べ替えます。配列に重複する組を含んではいけません。
解答
threeSum(nums) {
const array = nums.sort((a, b) => a - b); // 昇順にソート
const threeArray = [];
for (let i = 0; i < array.length - 2; i++) {
// 重複をスキップ
if (i > 0 && array[i] === array[i - 1]) continue;
let left = i + 1;
let right = array.length - 1;
while (left < right) {
const sum = array[i] + array[left] + array[right];
if (sum === 0) {
// 条件を満たした場合
threeArray.push([array[i], array[left], array[right]]);
left++;
right--;
// 重複をスキップ
while (left < right && array[left] === array[left - 1]) left++;
while (left < right && array[right] === array[right + 1]) right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return threeArray;
}
解説
計算量をO(n^2)とする為に、「Two Pointers法」を採用します。まずは値を昇順にソートを行うことで、同じ値は必ず隣り合って並びます。array[left] === array[left - 1]またはarray[right] === array[right + 1]を設定することで、次の値の重複をスキップします。
左ポインタと右ポインタを操作して、値を比較していきます。ちなみに、二重ループ（Brute Force）による解法の場合、計算量がO(n^3)となります。
threeSum(nums) {
const res = new Set();
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
for (let k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] === 0) {
res.add(JSON.stringify([nums[i], nums[j], nums[k]]));
}
}
}
}
return Array.from(res).map(item => JSON.parse(item))
}
JSON.stringifyを使用する理由
new Set()重複する要素を自動的に取り除くデータ構造ではありますが、プリミティブな値や文字列しか保存できないため、三つ組みの配列 [nums[i], nums[j], nums[k]] をそのままSetに追加すると、配列が重複しているかどうかを認識でききません（JavaScriptでは配列は異なるオブジェクトとして判断されます。）JSON.stringifyは配列をJSON文字列に変換するため、内容が同じ配列が同じ文字列として認識されるようになり、例えば、[1, 2, -3] と [1, 2, -3] はどちらも "["1", "2", "-3"]" という同じ文字列に変換されます。これによりSetは内容が同じ三つ組みを重複として認識することが可能です。
13. Container With Most Water
You are given an integer array heights where heights[i] represents the height of the ith bar.
You may choose any two bars to form a container. Return the maximum amount of water a container can store.
heights配列が与えられ、それぞれバーの高さが格納されている。二つのバーを選択して容器が保存できる水の最大量を返す。
解答
▪️二重ループ（Brute Force）の場合
maxArea(heights) {
let res = 0;
for (let i = 0; i < heights.length; i++) {
for (let j = i + 1; j < heights.length; j++) {
res = Math.max(res, Math.min(heights[i], heights[j]) * (j - i));
}
}
return res;
}
▪️ Two Pointerの場合
maxArea(heights) {
let res = 0;
let left = 0; // 左ポインタ
let right = heights.length - 1; // 右ポインタ
while (left < right) {
res = Math.max(res, Math.min(heights[left], heights[right]) * (right - left));
if (heights[left] < heights[right]) {
left++;
} else {
right--;
}
}
return res;
}
}
解説
二重ループの場合は、for文で１箇所づつ値を比較します。Math.min高さが低い方に合わせて、お互いのバーの距離を踏まえて計算し、最大の積載量を求めます。ただ計算量が𝑂(𝑛2)であるため、大きな配列に対しは非効率的です。
Tow Pointerの場合は、初期の位置をleftとrightに格納して、最大面積をmin(left, right)*(left - right)で計算します。条件に従って left、rightを内側に移動し、最大面積を更新します。
14. Valid Parentheses
You are given a string s consisting of the following characters: '(', ')', '{', '}', '[' and ']'.
The input string s is valid if and only if:
Every open bracket is closed by the same type of close bracket.
Open brackets are closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
'(', ')', '{', '}', '['の文字からなるsが引数として渡される。以下の条件に当てはまる場合はtrueとなる。
- どの開き括弧も、同じ種類の閉じ括弧で閉じられている。
- どの開き括弧も、正しい順序で閉じられている。
- どの閉じ括弧も、対応する同じ種類の開き括弧を持っている。
解答
isValid(s) {
const validStack = []
const closeToOpen = {
')': '(',
']': '[',
'}': '{'
}
for(let b of s){
if(closeToOpen[b]) {
if(validStack.length > 0 && validStack[validStack.length - 1] === closeToOpen[b]){
validStack.pop()
} else {
return false
}
} else {
validStack.push(b)
}
}
return validStack.length === 0
}
解説
closeToOpenで開き括弧と閉じ括弧の対応表を作成します。一致する閉じ括弧が存在しない場合は、validStackに格納され、一致した場合に、同じ閉じ括弧かどうかを判定します。
15. min stack
Design a stack class that supports the push, pop, top, and getMin operations.
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
Each function should run in O(1) O(1) time.
以下の機能を持つスタックを作成する。
- push(x) -- スタックに要素xをpushする
- pop() -- スタックの一番上から要素を取り除く
- top() -- 一番上の要素を取得する
- getMin() -- スタック内の最小要素を定数時間で返す
解答
class MinStack {
constructor() {
this.stack = []; // スタック
this.minStack = []; // スタックの最小要素
}
push(val) {
this.stack.push(val)
if(this.minStack.length === 0) {
this.minStack.push(val)
} else {
this.minStack.push(Math.min(this.minStack[this.minStack.length - 1],val))
}
}
pop() {
this.stack.pop()
this.minStack.pop()
}
top() {
return this.stack[this.stack.length - 1]
}
getMin() {
return this.minStack[this.minStack.length - 1]
}
}
解説
スタックと最小単位を格納する変数を設定
this.stack = []; // スタック
this.minStack = []; // スタックの最小要素
popとpushについてはそのままの実装が可能。
push(val) {
this.MinStack.push(val)
}
pop() {
this.MinStack.pop()
}
定数時間について： 定数時間とは問題の計算にかかる時間が入力として与えられるデータの大きさに依存せず一定であることを指します。つまり、pushやpopの処理をgetMin()で呼び出した場合、定数時間の条件には当てはまらなくなってしまう。pushする際は現在の最小値と追加される値を比較して小さい方を保持します。
push(val) {
this.stack.push(val)
if(this.minStack.length === 0) {
this.minStack.push(val)
} else {
this.minStack.push(Math.min(this.minStack[this.minStack.length - 1],val))
}
}
pop() {
this.stack.pop()
this.minStack.pop()
}
16. Evaluate Reverse Polish Notation
You are given an array of strings tokens that represents a valid arithmetic expression in Reverse Polish Notation.Return the integer that represents the evaluation of the expression.
The operands may be integers or the results of other operations.
The operators include '+', '-', '*', and '/'.
Assume that division between integers always truncates toward zero.
stringの配列で渡された値を算術（逆ポーランド記法を使用）する。
逆ポーランド記法とは・・・普段私たちが使用している中置記法は演算の優先順位を考慮したり、カッコの中を先に演算したりする必要があるので、プログラムで処理しにくい。「逆ポーランド記法」は、プログラムで処理しやすいものであり、「AB＋」のように、値と値の後に演算子を置きます。
【逆ポーランド記法の計算式の値を得る手順】
（1） 逆ポーランド記法の計算式の先頭から順に1文字ずつ取り出す。
（2） 取り出した文字が値（変数や数値）ならスタックにプッシュする。
（3） 取り出した文字が演算子ならスタックから2つのデータをポップし、両者の演算結果の値をスタックにプッシュする。
（4） （1）に戻って繰り返し、最後の文字を取り出して処理したら、その時点でスタックに残っている1つの値が計算式の値である。
解答
class Solution {
/**
* @param {string[]} tokens
* @return {number}
*/
evalRPN(tokens) {
if(!tokens.length) {
return 0
}
const stack = []
for(const token of tokens) {
switch(token) {
case '+':
stack.push(stack.pop() + stack.pop())
break
case '-':
stack.push(-stack.pop() + stack.pop())
break
case '*':
stack.push(stack.pop() * stack.pop())
break
case '/':
stack.push(Math.trunc(1 / stack.pop() * stack.pop()))
break
default: stack.push(Number(token))
}
}
const result = stack.pop()
return result
}
}
解説
逆ポーランド記法の数式の計算
tokenが数値以外の場合は計算式を適用し、pop()で取り出し計算します。逆に数値の場合はpushしてstacksいておおて、整数同士の割り算は常にゼロに向かって切り捨てられることが条件の為、Math.trunc()で引数として与えた数の小数部の桁を取り除きます。
17. daily-temperatures
You are given an array of integers temperatures where temperatures[i] represents the daily temperatures on the ith day.
Return an array result where result[i] is the number of days after the ith day before a warmer temperature appears on a future day. If there is no day in the future where a warmer temperature will appear for the ith day, set result[i] to 0 instead.
整数の配列 temperatures が与えられます。この配列の各要素temperatures[i]は、i日目の気温を表しています。戻り値としての配列resultではresult[i] は、i日目よりも後に、より暖かい日が現れるまでに何日待つ必要があるかを表します。もし、i日目以降により暖かい日が存在しない場合は、result[i]を0にします。
解答
dailyTemperatures(temperatures) {
if(!temperatures.length) return
const result = new Array(temperatures.length).fill(0)
const stack = []
for (let i = 0; i < temperatures.length; i++) {
while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
const prevIndex = stack.pop() // 末尾のインデックスの取り出し
result[prevIndex] = i - prevIndex
}
stack.push(i)
}
return result
}
解説
二重ループでも対応可能ですが、計算量が O(n²)になる為、 O(n)に抑えたいと思います。
単調スタック（Monotonic Stack）を使用します。単調スタックとは、要素が単調（増加 or 減少）な順序で並ぶように管理するスタックで、コーディング面接などによく使用されます。過去の要素に対して、将来の条件（次に大きい値や小さい値を）を満たす値を高速に探したいときに使用します。
stackは値ではなくindexを保持しており、スタックに今まで積み上げてきた日（過去の未解決のインデックス）に対して、今日の気温（temperatures[i]）が高いかどうかを判定します。
Discussion